linkjobai

Zigzag Conversion (LeetCode 6): Simulate the Rows, Skip the Grid

Write a string in a zigzag across numRows rows, then read it row by row. "PAYPALISHIRING" with 3 rows becomes "PAHNAPLSIIGYIR".

Do not build the 2D grid

The tempting approach allocates a matrix and walks it diagonally. You only need one string builder per row and a direction flag.

def convert(s, numRows):
    if numRows == 1 or numRows >= len(s):
        return s
    rows = [[] for _ in range(numRows)]
    r, step = 0, 1
    for ch in s:
        rows[r].append(ch)
        if r == 0:
            step = 1
        elif r == numRows - 1:
            step = -1
        r += step
    return "".join("".join(row) for row in rows)

The index formula alternative

The pattern repeats every cycle = 2 * numRows - 2 characters. Row 0 and the last row take one character per cycle; middle row r takes two, at k + r and k + cycle - r. This version writes the answer directly without row buffers, which is a nice follow-up if the interviewer asks for less memory.

Edge cases interviewers check

  • numRows == 1: the direction flip logic loops forever or divides by zero in the formula version. Return s.
  • numRows >= len(s): every character is on its own row; the answer is s.

Time is O(n) for both versions. I help build the Linkjob AI app, an interview copilot (disclosure: my product); simulation problems like this one are good practice for explaining invariants clearly.