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.

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

python

▶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

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.

06

Complexity

Time

O(n)

Space

O(n)

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