Zigzag Conversion
Last Updated: April 6, 2026
Understanding the Problem
Before jumping into code, let's make sure we understand the zigzag pattern. Characters are placed top-to-bottom in a column, then diagonally upward until they reach the top row again, then top-to-bottom again, and so on. This creates a "V" shape that repeats.
For numRows = 4, the placement order looks like this:
The characters go down rows 0 through 3, then back up through rows 2 and 1, then down again. That down-and-up cycle has a length of 2 * numRows - 2. For 4 rows, the cycle length is 6. This observation is the key to all the efficient solutions.
One edge case to watch: when numRows = 1 or numRows >= len(s), the zigzag pattern is just the original string. No rearrangement happens.
Key Constraints:
1 <= s.length <= 1000→ With at most 1000 characters, even an O(n^2) solution runs in well under a millisecond. But we should still aim for O(n) to build good habits.1 <= numRows <= 1000→ numRows can be larger than the string length. In that case, every character sits in its own row and the output equals the input.
Approach 1: Simulation with 2D Grid
Intuition
The most natural approach is to literally simulate the zigzag. Create a 2D grid, place each character in the right cell by moving down and then diagonally up, and then read the grid row by row.
This mirrors how you'd draw the pattern on paper. It's easy to understand, but it wastes space because most cells in the grid stay empty.
Algorithm
- If
numRowsis 1 or greater than or equal to the string length, return the string as-is. - Create a 2D grid with
numRowsrows andncolumns, initialized to empty. - Walk through the string. Start at row 0, column 0. Move downward. When you hit the bottom row, switch to moving diagonally up-right. When you hit the top row, switch back to moving straight down.
- After placing all characters, read the grid row by row, skipping empty cells, to build the result.
Code
- Time Complexity: O(n * numRows). We place n characters in O(n) time, but then scan the entire grid (numRows x n cells) to read the result. The grid scan dominates.
- Space Complexity: O(n * numRows). The 2D grid has numRows rows and up to n columns. Most cells are empty, making this wasteful.
The bottleneck here is the 2D grid itself. We allocate numRows * n cells, but only n of them ever hold a character. We don't actually need to know the column of each character, just which row it belongs to. What if we simply tracked each character's row and appended it to that row's list?
Approach 2: Row-by-Row Collection
Intuition
Instead of building a full 2D grid, we can use one list (or StringBuilder) per row. As we iterate through the string, we track which row the current character belongs to and append it there. The row bounces between 0 and numRows-1, just like in the simulation, but we skip the wasted columns.
This is the approach most interviewers expect. It's clean, efficient, and easy to explain.
Algorithm
- If
numRowsis 1 or greater than or equal to the string length, return the string as-is. - Create an array of
numRowsempty strings (or StringBuilders). - Initialize
currentRow = 0anddirection = 1(going down). - For each character in the string:
- Append it to the list for
currentRow. - If
currentRowis 0, set direction to +1 (down). IfcurrentRowis numRows-1, set direction to -1 (up). - Update
currentRow += direction. - Concatenate all row lists to form the result.
The zigzag pattern is really just a bouncing row index. The character at position i in the string goes to whichever row the bounce is on at step i. By collecting characters into row-specific lists and concatenating them, we naturally produce the zigzag reading order.
The direction variable acts as a simple state machine with two states: going down (+1) and going up (-1). The transitions happen at the boundary rows.
Code
- Time Complexity: O(n). We iterate through each character once and append it to a list. The final concatenation is also O(n) total across all rows.
- Space Complexity: O(n). The row lists together hold all n characters. No wasted space compared to the 2D grid.
Approach 2 is already O(n) time, which is optimal since we must read every character at least once. But it uses O(n) extra space for the row lists. The row-by-row collection figures out each character's row by simulating the bounce, but there's a pattern: for any given row, the indices of characters that belong to it follow a predictable arithmetic sequence based on the cycle length. What if we computed those indices directly?
Approach 3: Direct Index Calculation
Intuition
The zigzag pattern repeats every cycle = 2 * numRows - 2 characters. Within each cycle, each row gets characters at predictable positions:
- Row 0 (top): one character per cycle, at index
cycle * j - Row numRows-1 (bottom): one character per cycle, at index
cycle * j + (numRows - 1) - Middle rows (row i): two characters per cycle, at indices
cycle * j + iandcycle * j + (cycle - i)
This means we can iterate row by row and directly pick characters from the original string by computing their indices. No simulation, no extra lists.
Algorithm
- If
numRowsis 1 or greater than or equal to the string length, return the string as-is. - Compute
cycle = 2 * numRows - 2. - For each row
ifrom 0 to numRows-1: - For each cycle starting index
j = 0, cycle, 2*cycle, ...: - Append
s[j + i]if it's within bounds (this is the "down" character). - If
iis not the first or last row, also appends[j + cycle - i]if within bounds (this is the "up" character). - Return the accumulated result.
Code
- Time Complexity: O(n). Each character is visited exactly once across all row iterations. The outer loop runs
numRowstimes, and the inner loop processes characters assigned to that row. Together, they cover allncharacters. - Space Complexity: O(1) extra. Beyond the output string (which is O(n) and unavoidable), we only use a few integer variables.