Zigzag Conversion

A visual zigzag is easy to draw and surprisingly easy to implement incorrectly. The reliable solution is smaller: track the current row, track the movement direction, and turn only at the two boundaries.

Read the Output Contract

The input provides a string s and a number of rows, numRows. Characters are consumed from left to right:

1. Move downward through the rows.
2. Move diagonally upward until reaching the top.
3. Repeat the path.
4. Read the characters row by row from top to bottom.

Every input character must appear exactly once in the output. Case and punctuation are ordinary data: a comma remains a comma, and a period remains a period.

The constraints are:

• 1 <= len(s) <= 1000
• 1 <= numRows <= 1000
• s contains English letters, commas, and periods.

The first decision determines the rest of the solution:

Do not build the visible picture unless the column positions affect the answer.

The final readout only depends on two facts:

• Which row received each character.
• The order in which characters entered that row.

The empty grid coordinates are irrelevant. Store one character list per row and discard the columns.

There is also an immediate identity case:

numRows == 1  ->  return s

With one row, there is nowhere to move. The input is already the row-by-row output.

Replace the Diagram with State

The recognition cue is a repeated path whose next step depends only on a small amount of current state:

• The input is scanned once from left to right.
• Each character belongs to exactly one row.
• The next row depends on the current row and whether movement is downward or upward.

That is a finite-state traversal. The moving part needs only two variables:

• current_row: the row that receives the next character.
• direction: +1 for downward movement and -1 for upward movement.

The output structure needs one bucket per row:

rows = [[] for _ in range(numRows)]

For each character:

1. Append it to rows[current_row].
2. Change direction if the current row is the top or bottom boundary.
3. Move one row in that direction.

At the end, join the buckets from row 0 through row numRows - 1.

A full two-dimensional grid is useful as a first mental model because it matches the drawing. It is a poor implementation model because it stores columns that the answer immediately throws away.

Simulate the output-relevant obligation, not the entire picture.

Derive the Boundary Rule

The safest update order is:

1. Place the current character.
2. Turn around if the current row is a boundary.
3. Move one row in the new direction.

Use this precise state convention:

Before processing each character, current_row is that character’s destination row, and direction describes the next one-row movement after the character is placed.

The boundaries determine the next movement:

• At row 0, the next movement must be downward.
• At row numRows - 1, the next movement must be upward.
• At an interior row, keep the current direction.

For numRows = 3, the destination rows are:

0, 1, 2, 1, 0, 1, 2, 1, 0, ...

The boundary character belongs to the boundary row before the turn occurs. This is why placement must happen first.

Suppose the current row is 2 in a three-row problem. The current character belongs in row 2. After placing it, reverse the direction and move to row 1. If you reverse before placement, that character goes into row 1, shifting every later character.

The one-row case deserves an early return because row 0 is simultaneously the top and bottom boundary. The ordinary transition would receive contradictory instructions and could produce an invalid next row.

Choose the Lean Simulation

A direct baseline is to build a sparse grid:

• Move down one row at a time.
• Move diagonally upward one row at a time.
• Record each character at its grid position.
• Read the grid row by row.

That approach mirrors the drawing, but most grid cells remain empty. Since column positions do not affect the output, the grid carries geometry that the result does not need.

The leaner string row simulation keeps only the row buckets:

1. Allocate one bucket per row.
2. Start at row 0, moving downward.
3. Append each character to its current row.
4. Reverse direction at row 0 or row numRows - 1.
5. Advance exactly one row.
6. Concatenate the buckets in ascending row order.

Each part answers a separate obligation:

• rows preserves the required row-by-row output.
• current_row identifies the destination of the next character.
• direction determines the next movement.
• The loop processes each input character exactly once.
• The final join reads the rows in the required order.

A cycle-length solution can jump directly to positions in each repeating zigzag cycle. It saves the row buckets, but requires deriving the cycle length, calculating the diagonal offset, and special-casing the top and bottom rows because they have no separate diagonal character. That approach is useful when direct indexing is the goal. For an interview, I would prefer row simulation here: it mirrors the contract, makes boundary behavior visible, and gives you fewer arithmetic failure points to debug.

Prove the Invariant

The algorithm is not correct merely because it matches a familiar pattern. Its correctness follows from a state invariant.

Placement

Before each iteration, assume:

• current_row is the correct row for the next character.
• direction describes the next one-row movement after placement, subject to a boundary turn.

Appending the character to rows[current_row] therefore places it in the correct row.

The initial state is correct: the first character starts at row 0.

Transition

After placement:

• If the current row is 0, set direction to +1.
• If the current row is numRows - 1, set direction to -1.
• Otherwise, leave direction unchanged.

Then update:

current_row = current_row + direction

At the top boundary, this moves into row 1. At the bottom boundary, this moves into row numRows - 2. At an interior row, it continues along the current leg.

The direction changes only at valid boundaries, so the next row remains within the range 0 through numRows - 1. The invariant is restored for the next character.

By induction, every character is placed in the row prescribed by the zigzag traversal.

Output

The required output is a row-by-row readout. Joining rows[0], then rows[1], and so on produces exactly that readout.

Preservation

Each input character is processed once and appended to exactly one bucket. No character is dropped, duplicated, filtered, or rewritten. Therefore, the output preserves the input length and character contents.

A sample demonstrates one path. The invariant explains every path.

Trace a Real Example

Use:

s = "PAYPALISHIRING"
numRows = 3

The state begins at row 0 and moves downward. The table records the destination row and the direction after each placement:

Character	Row	Direction after placement	Buckets
P	0	down	P, ,
A	1	down	P, A, ``
Y	2	up	P, A, Y
P	1	up	P, AP, Y
A	0	down	PA, AP, Y
L	1	down	PA, APL, Y
I	2	up	PA, APL, YI
S	1	up	PA, APLS, YI
H	0	down	PAH, APLS, YI
I	1	down	PAH, APLSI, YI
R	2	up	PAH, APLSI, YIR
I	1	up	PAH, APLSII, YIR
N	0	down	PAHN, APLSII, YIR
G	1	down	PAHN, APLSIIG, YIR

The final buckets are:

row 0: PAHN
row 1: APLSIIG
row 2: YIR

Joining them produces:

PAHNAPLSIIGYIR

The trace makes the direction convention concrete:

• After placing P at the top, the next movement is down.
• After placing Y at the bottom, the next movement is up.
• After placing the second A at the top, the next movement is down again.

The state changes at the boundary, but the boundary character is never moved out of its row.

Implement the Python Solution

Use lists while scanning and join once at the end. The lists make the row state explicit, while the final join performs the required row-by-row readout.

def convert(s: str, numRows: int) -> str:
    if numRows == 1:
        return s

    rows = [[] for _ in range(numRows)]
    current_row = 0
    direction = 1  # +1: down, -1: up

    for char in s:
        # The current state identifies this character's destination.
        rows[current_row].append(char)

        # Turn after placing a boundary character.
        if current_row == 0:
            direction = 1
        elif current_row == numRows - 1:
            direction = -1

        current_row += direction

    return "".join("".join(row) for row in rows)

The code follows the derivation directly:

• rows stores output-relevant row membership.
• current_row identifies where the next character belongs.
• direction controls the next one-row movement.
• char is opaque input; no case conversion or punctuation filtering occurs.
• The boundary test happens after placement.

The interview checklist is short:

• Return immediately for numRows == 1.
• Place before turning.
• Turn only at row 0 and row numRows - 1.
• Move exactly one row.
• Join rows in ascending order.

An input with numRows >= len(s) also returns unchanged. The traversal cannot revisit a row before the input ends, so every character lands in a distinct early row. The remaining row buckets are empty, and joining them still returns the original string.

Test Boundaries and Complexity

Let:

n = len(s)
r = numRows

The scan processes each character once. The final joins process the stored characters once and iterate across the row structure.

For this implementation:

• Time complexity: O(n + r)
• Auxiliary space: O(n + r)

The + r terms matter because the code allocates one empty list for every requested row, even when there are more rows than characters. The n term accounts for storing the characters in those buckets. Under the stated constraints, r can exceed n, so the literal complexity of this implementation should remain O(n + r). The character storage itself is O(n).

Test the boundaries deliberately.

One row

convert("PAYPALISHIRING", 1)
# "PAYPALISHIRING"

No movement should occur.

More rows than characters

convert("abc", 5)
# "abc"

The buckets are:

row 0: a
row 1: b
row 2: c
row 3:
row 4:

Joining them returns the original string, and no invalid row is accessed.

Mixed case and punctuation

convert("a,B.c", 3)
# "ac,.B"

The placement sequence is:

row 0: a c
row 1: , .
row 2: B

Reading the rows gives ac,.B. The comma, period, uppercase B, and lowercase letters all survive because the algorithm treats every character uniformly.

Also test:

• The canonical multi-row example.
• A very short string.
• An input that ends during the upward leg.
• numRows = 2, where movement alternates between the two rows.

The common failures are predictable:

• Turning before placing a boundary character.
• Advancing by more than one row during the upward leg.
• Forgetting the special case for one row.
• Assuming every character is a lowercase letter.
• Building a full sparse grid when only row membership is needed.
• Joining rows in the wrong order.
• Using a direction convention in the explanation that does not match the code.

The Transferable Pattern

When a scan follows a repeated path, ask:

What is the smallest state that determines where the next item goes and what transition comes after it?

For Zigzag Conversion, that state is:

current row + direction

The diagram helps you see the motion. The invariant makes the motion reliable. Track the state, place the item, turn at the boundary, and test the edges before submitting.

That is the reusable move: when the visible structure contains more geometry than the output needs, compress the geometry into the smallest state that preserves the required order.