Zigzag Conversion
Write a string in a zigzag pattern and read it row by row, by simulating the bouncing direction
Problem Statement
Write a string in a zigzag pattern across a given number of rows, then read it row by row.
s = "PAYPALISHIRING", numRows = 3
P A H N
A P L S I I G
Y I R
Read row by row → "PAHNAPLSIIGYIR"s = "PAYPALISHIRING", numRows = 4
P I N
A L S I G
Y A H R
P I
Read row by row → "PINALSIGYAHRPI"Intuition
The picture suggests building a 2-D grid, but you never need one — only which row each character lands on.
The key insight
Walk the string once, appending each character to a bucket for its current row. Track the row index and a direction:
- Move down: row increases by 1
- Move up: row decreases by 1
- Flip direction at the top row (
0) and the bottom row (numRows - 1)
At the end, concatenate the buckets top to bottom.
The zigzag is just a bouncing counter. Columns, spacing and the visual layout are irrelevant — reading row by row discards all of that anyway.
Real-world analogy
A typewriter that reverses direction at each margin. You do not need to know the page layout to say which line a character lands on — you only need to know which way the carriage is currently moving.
Watch it run
Approach
Handle numRows == 1
There is no zigzag with one row — return the string unchanged. Without this guard the direction never flips and the row index runs out of bounds.
Walk the string
Append each character to rows[current], then move current by the step.
Flip the step at either boundary
When current is 0 or numRows - 1, negate the step.
Solution
def convert(s: str, num_rows: int) -> str:
"""Write s in a zigzag across num_rows rows, then read row by row."""
if num_rows == 1 or num_rows >= len(s):
return s # no zigzag happens — nothing to rearrange
rows = [[] for _ in range(num_rows)]
current = 0
step = 1 # +1 moving down, -1 moving up
for char in s:
rows[current].append(char)
# Flip direction at the top and bottom rows.
if current == 0:
step = 1
elif current == num_rows - 1:
step = -1
current += step
return "".join("".join(row) for row in rows)Set the direction before moving, not after
Checking the boundary after incrementing lets current briefly go out of range. Deciding the step while standing on the boundary row keeps every index valid.
Also note the order of the two branches: with numRows = 2, row 0 and row numRows - 1 = 1 are both boundaries, and testing current == 0 first gives the correct downward bias.
The closed-form alternative
There is a formula-based solution that computes each row's characters directly using a cycle length of 2 × numRows - 2. It avoids the buckets, but the index arithmetic — especially for the diagonal characters in the middle rows — is fiddly and easy to get wrong. The simulation is the same O(n) and far easier to defend in an interview.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
- Time — each character is placed once and read once.
- Space — the buckets together hold exactly
ncharacters, plus the output string.
Edge Cases
Related Problems
- Text Justification — another layout-simulation problem, with harder rules
- Reverse Words in a String — rearranging string content
- Simplify Path — string processing driven by simple state