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

The intuition first. You could allocate an actual numRows × len(s) character grid, walk the zigzag placing each character at its true (row, col), then read non-empty cells row by row.

class Solution:
    def convert(self, 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 clarifies the geometry but the row buffers below drop the wasted columns.

Approach 2 — Row buffers, bounce at the edges

The insight: you never need real columns. Just append each character to a buffer for its current row; the column ordering within a row is automatically the visitation order. Move the row pointer +1 going down, -1 going up, flipping direction whenever you reach row 0 or row numRows - 1.

class Solution:
    def convert(self, 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 insight: 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 — for the middle rows — a second “up” character at offset cycle - r. So you can emit each row directly by striding through s.

class Solution:
    def convert(self, 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 and up offsets 1+3=4? no, base+cycle-r: for base=0, up = 3; base=4, up = 7; base=8, up = 11; base=12, up = 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 reward spotting the period. Once you know one cycle spans 2·numRows − 2 characters, index arithmetic pinpoints exactly which source positions land in each row — replacing simulation with direct addressing. When the arithmetic is fiddly, the “simulate and bounce a pointer” fallback is always O(n) and easy to trust.