Zigzag Conversion
Zigzag Conversion: read a string written in a zigzag pattern across numRows rows, row by row.
- 1 <= s.length <= 1000
- s consists of English letters (lower-case and upper-case), ',' and '.'.
- 1 <= numRows <= 1000
Intuition
Zigzag conversion writes a string in a zigzag across numRows rows, then reads it off row by row. The visual description invites simulating a 2D grid, which is both wasteful and fiddly.
The simplification is that the grid is never needed:
- Only which row each character belongs to matters, so keep one string per row and append each character to the right one.
Walking the input once, the row index moves down to numRows − 1, then back up to 0, then down again. Tracking a direction variable that flips at both boundaries produces exactly that motion.
The direction must reverse at both the top and the bottom. Flipping only at the bottom sends the index negative; only at the top and it runs past the last row.
Joining the rows in order gives the answer, with no padding, no grid, and no positional arithmetic.
The case that breaks most solutions is numRows == 1. There is no zigzag — the string is returned unchanged. With a direction variable, the index would otherwise oscillate incorrectly or the flip logic would divide the single row wrongly, so this needs an explicit early return.
A numRows at least as large as the string also degenerates safely: each character occupies its own row and the output equals the input.
The mathematical alternative computes each row's characters directly from index arithmetic, using a cycle length of 2 × numRows − 2. It avoids the row buffers but the index formulas — particularly for the diagonal characters in the middle rows — are easy to get wrong for little gain.
One pass gives O(n) time and O(n) space for the row buffers.
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.
Approach
Before reading on: price up what the direct approach costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(n) time and O(n) space.
Drop the grid
Only each character's row matters, not its column. One string per row replaces the 2D simulation entirely.
Track the row and direction
Walk the input appending to the current row, moving the index down then up. A direction variable produces the zigzag motion.
Flip at both boundaries
Reverse direction at the top and the bottom. Flipping only at the bottom sends the index negative; only at the top overruns the last row.
Handle a single row
numRows == 1 has no zigzag — return the string unchanged. The direction logic misbehaves on one row, so this needs an explicit early return.
Join the rows in order
Concatenate the row buffers top to bottom. No padding or positional arithmetic is required.
Note the arithmetic alternative
Characters can be indexed directly with a cycle of 2 × numRows − 2, but the formulas for the middle rows' diagonal characters are error-prone for little gain.
Cost of the approach
One pass appending each character once gives O(n) time and O(n) space for the row buffers.
Solution & live demo
Common pitfalls
Not special-casing one row
rows = [''] * numRows cur, step = 0, -1
if numRows == 1:
return sWith 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
cur += step
if cur == 0 or cur == numRows - 1:
step = -stepif cur == 0 or cur == numRows - 1:
step = -step
cur += stepThe 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
cycle = 2 * numRows - 2 row = i % cycle if ... else ...
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.
Edge cases
Return the input string unchanged; the zigzag walk never flips direction with only one row.
Every character lands on its own row going straight down; direction never flips upward, output equals input.
Single character placed on row 0, loop ends immediately, answer is that one character.
Direction flips every single step since row 0 and row 1 are both boundaries, producing an alternating placement.