Zigzag Conversion

Problem

Take a string s and write it out in a zigzag pattern across a fixed number of rows numRows, moving down the rows then diagonally back up, repeatedly. Then read the grid row by row (left to right, top to bottom) and return that as a single string.

For example, "PAYPALISHIRING" with 3 rows is laid out as:

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

Reading row by row gives "PAHNAPLSIIGYIR".

Examples

• s = "PAYPALISHIRING", numRows = 3 → "PAHNAPLSIIGYIR".
• s = "PAYPALISHIRING", numRows = 4 → "PINALSIGYAHRPI" — the pattern goes down 4, then diagonally up.
• s = "AB", numRows = 1 → "AB" — one row means no zigzag; the string is unchanged.

Constraints

• 1 <= len(s) <= 1000
• s consists of English letters (upper/lower), commas, and periods.
• 1 <= numRows <= 1000
• When numRows == 1 (or numRows >= len(s)), there is no zigzag and the output equals the input.

Think about it first

TL;DR

Simulate the zigzag with one buffer per row (bounce direction at the edges) — O(n) time, O(n) space. A cycle-arithmetic variant needs no per-row buffers.

Approach 1 — Brute force: build the 2-D grid literally

Allocate a numRows × len(s) character grid, walk the zigzag placing each character at its (row, col), then read the non-empty cells row by row.

def convert(s: str, numRows: int) -> str:
    if numRows == 1:
        return s
    grid = [[""] * len(s) for _ in range(numRows)]
    row, col, going_down = 0, 0, False
    for ch in s:
        grid[row][col] = ch
        if row == 0 or row == numRows - 1:
            going_down = not going_down
        if going_down:
            row += 1
        else:                    # moving diagonally up-right
            row -= 1
            col += 1
    return "".join(ch for r in grid for ch in r if ch)

Complexity: O(numRows · n) time and space. The grid is mostly empty, so this wastes memory. It makes the geometry explicit; the row buffers in Approach 2 drop the wasted columns.

Approach 2 — Row buffers, bounce at the edges

You never need real columns. Append each character to a buffer for its current row; within a row, append order is already the left-to-right order. Move the row pointer +1 going down and -1 going up, flipping direction whenever you reach row 0 or row numRows - 1.

flowchart LR
    T["Row 0<br/>step = +1"] -->|move down| M["Middle rows"]
    M -->|reach bottom| B["Row numRows-1<br/>step = -1"]
    B -->|move up| M
    M -->|reach top| T

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

    rows = [[] for _ in range(numRows)]
    row, step = 0, 1
    for ch in s:
        rows[row].append(ch)
        if row == 0:
            step = 1
        elif row == numRows - 1:
            step = -1
        row += step

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

Walkthrough with s = "PAYPALISHIRING", numRows = 3:

• Rows fill as the pointer bounces 0,1,2,1,0,1,2,1,0,...:
  • row 0 gets indices 0, 4, 8, 12 → P, A, H, N
  • row 1 gets 1, 3, 5, 7, 9, 11, 13 → A, P, L, S, I, I, G
  • row 2 gets 2, 6, 10 → Y, I, R
• Concatenate rows: "PAHN" + "APLSIIG" + "YIR" = "PAHNAPLSIIGYIR". Matches.

Complexity: O(n) time, O(n) space (the buffers together hold each character once).

Approach 3 — Cycle arithmetic (no buffers)

The zigzag is periodic. One full cycle (down then back up) covers cycle = 2 * numRows - 2 characters. Within a cycle, row r receives the down character at offset r, and the middle rows receive a second up character at offset cycle - r. So you can emit each row directly by striding through s.

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

    n = len(s)
    cycle = 2 * numRows - 2
    out = []
    for r in range(numRows):
        for base in range(0, n, cycle):
            down = base + r
            if down < n:
                out.append(s[down])
            # middle rows also get the diagonal "up" character
            if r != 0 and r != numRows - 1:
                up = base + cycle - r
                if up < n:
                    out.append(s[up])
    return "".join(out)

Walkthrough with numRows = 3 → cycle = 4:

• Row 0: offsets 0, 4, 8, 12 → P, A, H, N.
• Row 1 (middle): down offsets 1, 5, 9, 13; up offsets base + cycle - r give 3, 7, 11 (from base = 0, 4, 8), while base = 12 yields 15, out of range. Interleaved: A, P, L, S, I, I, G.
• Row 2: offsets 2, 6, 10 → Y, I, R.
• Same "PAHNAPLSIIGYIR".

Complexity: O(n) time, O(n) for the output only — no per-row storage.

Common pitfalls

• Forgetting the numRows == 1 guard: cycle = 0 causes a zero-length stride (infinite loop) in Approach 3, and the bounce logic in Approach 2 never advances.
• Adding the diagonal “up” character for the top or bottom row — only the middle rows have two characters per cycle.
• Flipping direction one step too late or too early; the direction must reverse at row 0 and row numRows - 1, before the next move.
• Assuming numRows >= len(s) needs special layout — it just returns s (every char on its own row).

Pattern takeaway

Periodic layout problems come down to finding the period. Once you know one cycle spans 2·numRows − 2 characters, index arithmetic pinpoints which source positions land in each row, replacing simulation with direct addressing. When the arithmetic is fiddly, the simulate-and-bounce fallback is still O(n) and easy to verify.