The Zigzag Encoder

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

A legacy message feed scrambles each payload with a zigzag layout before shipping it. The characters of s go one at a time down num_rows rows, then diagonally back up to the top, then down again, until the message runs out: with num_rows of 3 they land on rows 1, 2, 3, 2, 1, 2, 3, 2, and so on. The encoded payload is the rows read top to bottom, each left to right. With a single row, s comes back unchanged.

The message snakes its way across the rails.

Example 1

Input:

s = "PAYPALISHIRING", num_rows = 3

Output:

"PAHNAPLSIIGYIR"

Example 2

Input:

s = "PAYPALISHIRING", num_rows = 4

Output:

"PINALSIGYAHRPI"

Worked solution and explanation

The bounce is the whole problem

This is an index-reflection problem wearing a cipher costume. Everyone sees that characters get spread across rows and read back row by row. What separates candidates is noticing that the path bounces off the bottom row instead of wrapping to the top. The row index climbs to num_rows - 1, then falls back toward 0, so one full cycle is 2 * num_rows - 2 characters long and every interior row gets hit twice. Reach for i % num_rows and you have encoded a grid: every non-trivial case comes back scrambled.

Wrap (wrong)
row = i % num_rows sends rows 0, 1, 2, 0, 1, 2 for 3 rows. The middle row gets one character per cycle, and 'PAYPALISHIRING' encodes to the wrong string.
Bounce (right)
Rows go 0, 1, 2, 1, 0, 1, 2 for 3 rows. The cycle is 4 long, row 1 is visited on the way down and on the way back, and the output is 'PAHNAPLSIIGYIR'.

Building it

Step 1: Return early when nothing can bend

If num_rows <= 1 there is nothing to bounce between, and if num_rows >= len(s) every character sits alone on its own row. Both read back as s itself, so return it before any other work. The first guard also keeps the cycle length 2 * num_rows - 2 from ever being 0.

Step 2: Walk the rows and flip at both edges

One list per row, filled in a single pass. Carry current_row and a going_down flag; after placing a character, flip the flag at row 0 and at row num_rows - 1, then step one row in the current direction. The flip has to happen at BOTH boundaries, or the pointer walks off the end.

Step 3: Read the rows back in order

Join each row's characters, then join the rows top to bottom. Collecting into lists and joining once keeps the pass linear instead of rebuilding strings per character.

Row buckets with a direction flip
def zigzag_encode(s: str, num_rows: int) -> str:
    if num_rows <= 1 or num_rows >= len(s):
        return s
    rows = []
    for i in range(num_rows):
        rows.append([])
    current_row = 0
    going_down = True
    for ch in s:
        rows[current_row].append(ch)
        if current_row == 0:
            going_down = True
        elif current_row == num_rows - 1:
            going_down = False
        if going_down:
            current_row += 1
        else:
            current_row -= 1
    parts = []
    for row in rows:
        parts.append("".join(row))
    result = "".join(parts)
    return result

One pass over s, one join per row, then one final join.

Common follow-up questions