LeetCode #6 Medium

Zigzag Conversion

Read a string written in a zigzag pattern across numRows rows, row by row.

stringsimulation

02

Intuition

The tempting move is to build the actual 2D grid and then read it off row by row - but you never need the grid at all. What you need is one string buffer per row and a single pointer that walks down through the rows then back up, appending the current character to whichever row the pointer is on. The direction only flips at the two boundary rows, row 0 and row numRows-1, so a sign flip there is the entire mechanism. The other trap: if numRows is 1, the pointer never reaches a second boundary, so the direction never flips - you must special-case numRows == 1 and return the string untouched, or the walk conceptually loops forever.

How to spot this pattern

Simulate the walk rather than compute positions. A row cursor bounces between 0 and numRows - 1, flipping direction at each end — so appending each character to its current row and joining the rows at the end produces the answer with no index arithmetic.

03

Approach

1

Guard the single-row case

If numRows is 1, there is no zigzag at all - every character sits on the same row, so the output equals the input. Handle this before starting the walk, since otherwise the direction-flip logic below never triggers and the row pointer just sits at 0.

2

Walk rows with a direction flag

Create numRows empty string buffers. Track a current row and a direction of +1 or -1. For each character in the input, append it to the buffer for the current row, then check if the current row is 0 or numRows-1; if so, flip the direction. Advance the row pointer by the direction.

3

Concatenate the buffers

Once every character has been placed, join the row buffers in order from row 0 to row numRows-1. That concatenation is exactly the zigzag read-off, produced without ever allocating a 2D array.

04

Solution & live demo

▶1class Solution:
▶2    def convert(self, s: str, numRows: int) -> str:
▶3        if numRows == 1:
▶4            return s
▶5        rows = [''] * numRows
▶6        cur, step = 0, -1
▶7        for ch in s:
▶8            rows[cur] += ch
▶9            if cur == 0 or cur == numRows - 1:
▶10                step = -step
▶11            cur += step
▶12        return ''.join(rows)

05

Common pitfalls

Not special-casing one row

✗ Wrong

rows = [''] * numRows
cur, step = 0, -1

✓ Right

if numRows == 1:
    return s

With a single row, cur == 0 and cur == numRows - 1 are both true, so step flips twice per character and stays at −1 — driving the cursor to index −1. The zigzag degenerates and the walk breaks.

Flipping the direction after moving

✗ Wrong

cur += step
if cur == 0 or cur == numRows - 1:
    step = -step

✓ Right

if cur == 0 or cur == numRows - 1:
    step = -step
cur += step

The turn has to happen while the cursor is on the boundary row, before the next move. Flipping afterwards lets it step past the edge first.

Deriving each character's row by formula

✗ Wrong

cycle = 2 * numRows - 2
row = i % cycle if ... else ...

✓ Right

rows[cur] += ch
cur += step

The closed form works but needs a careful case split for the diagonal half of each cycle. Simulating the bounce is shorter and has one obvious edge case instead of several subtle ones.

06

Edge cases

numRows == 1

Return the input string unchanged; the zigzag walk never flips direction with only one row.

numRows >= len(s)

Every character lands on its own row going straight down; direction never flips upward, output equals input.

s has length 1

Single character placed on row 0, loop ends immediately, answer is that one character.

numRows == 2

Direction flips every single step since row 0 and row 1 are both boundaries, producing an alternating placement.

07

Complexity

Time

O(n)

Space

O(n)

n is the length of the string; each character is placed into a row buffer exactly once.