Zigzag Conversion: Reading a Pattern Row by Row

LeetCode 6, Zigzag Conversion, asks you to take a string and rearrange its characters into a zigzag pattern across a given number of rows, then read the result line by line.

For example, given "PAYPALISHIRING" with numRows = 3, the characters are placed like this:

P   A   H   N
A P L S I I G
Y   I   R

Reading each row left to right gives "PAHNAPLSIIGYIR".

The pattern looks complex at first glance, but the algorithm to produce it is short. You do not need to build a 2D grid. You just need to figure out which row each character belongs to, and a direction flag handles that.

The approach: row-by-row simulation

The key insight is that as you walk through the input string, the row index bounces between 0 and numRows - 1. You start at row 0, move downward until you hit the last row, then reverse direction and move upward until you hit row 0 again. This bounce repeats for the entire string.

Here is the plan:

1. Create a list of numRows empty strings (one per row).
2. Walk through each character in the input.
3. Append the character to the string for the current row.
4. If the current row is 0, set the direction to downward. If the current row is numRows - 1, set the direction to upward.
5. Move to the next row based on the direction.
6. After processing all characters, concatenate all row strings together.

That is the entire algorithm. The direction flag (+1 for down, -1 for up) does all the work of distributing characters into the right rows.

The code

def convert(s, numRows):
    if numRows == 1 or numRows >= len(s):
        return s

    rows = [""] * numRows
    cur_row = 0
    going_down = False

    for char in s:
        rows[cur_row] += char
        if cur_row == 0 or cur_row == numRows - 1:
            going_down = not going_down
        cur_row += 1 if going_down else -1

    return "".join(rows)

Walk through what happens:

1. Handle the two trivial cases: if numRows is 1, every character stays on the same row so the string is unchanged. If numRows is at least as large as the string length, there is no zigzag to speak of and the string is also unchanged.
2. Create numRows empty strings.
3. For each character, append it to the current row's string.
4. When the current row is 0 (top) or numRows - 1 (bottom), flip the direction. This is the bounce.
5. Move cur_row up or down by 1 based on the direction.
6. Join all row strings together for the final answer.

Visual walkthrough

Let's trace through "PAYPALISHIRING" with numRows = 3, showing how characters land in each row and how the direction flips at the boundaries.

The direction flag does all the heavy lifting. Every time the current row hits 0 or numRows - 1, the flag flips, and the row index starts moving the other way.

Why not use a 2D grid?

You could allocate a 2D array and place each character at its exact (row, column) position. That works, but it wastes space on empty cells. In the zigzag pattern, diagonal positions only have one character per column, leaving most cells in those columns empty. The row-by-row simulation avoids this entirely by only storing the characters that actually exist.

Complexity analysis

You visit each character exactly once and append it to one of the row strings. The final join is also O(n). No nested loops, no extra passes.

Building blocks

This problem is built from two fundamental techniques that show up across many string and simulation problems.

Direction flag (bounce pattern)

The idea of using a boolean or integer flag to reverse direction at boundaries is a reusable pattern. You see it in problems where an index needs to oscillate between two endpoints. The flag flips at each boundary, and a single +1 or -1 controls the movement.

Other problems that use this pattern:

• Spiral Matrix (LeetCode 54) uses direction changes to traverse a matrix in a spiral.
• Sort Colors (LeetCode 75) uses pointers that move inward from both ends.

Row bucket accumulation

Instead of building a 2D grid and reading it, you accumulate characters directly into per-row buckets. This avoids wasted space and simplifies the read step to a simple concatenation. Any time you need to reorder characters by some grouping criterion, collecting into buckets first is a clean approach.

Other problems that use this pattern:

• Group Anagrams (LeetCode 49) groups strings into buckets by their sorted key.
• Top K Frequent Elements (LeetCode 347) uses bucket sort to group elements by frequency.

Edge cases

numRows = 1. Every character goes into the same row. The output is identical to the input. The code handles this with an early return.

numRows >= len(s). There are enough rows that every character goes on its own row. The zigzag never bounces back, so the output is again identical to the input. Also handled by the early return.

numRows = 2. The zigzag alternates between row 0 and row 1 with no middle rows. For "ABCDEF" this produces "ACEBDF" (even-indexed characters on row 0, odd-indexed on row 1).

Single character. A string of length 1 with any numRows returns the string unchanged. The loop runs once and the join produces that single character.

Empty string. If s is empty, the early return for numRows >= len(s) triggers (since numRows >= 0), returning the empty string.

From understanding to recall

You can follow this solution step by step and it makes complete sense. But two weeks from now, when you sit down to solve it from scratch, the details that slip away are the small ones: initializing going_down to False so that the first flip at row 0 sets it to True, the condition cur_row == 0 or cur_row == numRows - 1 that triggers the flip, and the early return for the trivial cases.

Spaced repetition locks these details into long-term memory. You drill the direction-flag bounce pattern and the row accumulation pattern separately, each taking a minute or two. After a few reps at increasing intervals, the pieces are automatic. When you see a zigzag or oscillation problem in an interview, you are not reconstructing the logic from first principles. You are assembling bricks you already own.

Related posts

• String to Integer (atoi) - Another medium string problem that benefits from a structured traversal approach
• Longest Common Prefix - A string problem where character-by-character scanning is the core technique