Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
A complete visual walkthrough of the zigzag pattern — from brute force simulation to the elegant row-builder approach.
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N A P L S I I G Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I
Example 3:
Input: s = "A", numRows = 1 Output: "A"
Constraints:
1 <= s.length <= 1000s consists of English letters (lower-case and upper-case), ',' and '.'.1 <= numRows <= 1000The most intuitive approach: build a 2D grid and actually place each character at its zigzag position. Then read the grid row by row, left to right.
Place characters in a zigzag pattern across 3 rows, then read each row left to right.
With 4 rows, the zigzag creates a deeper pattern with diagonal characters between the top and bottom.
This approach works but wastes space. The 2D grid has many empty cells. For a string of length n with numRows rows, the grid can be up to O(n * numRows) in size, even though most cells are empty.
The waste: We allocate an entire 2D grid just to figure out which characters end up in which row. But we never actually need the column positions — we just need the row assignments. Can we skip the grid entirely?
You don't need a 2D array at all. The zigzag pattern is just a bouncing counter: start at row 0, go down to row numRows-1, then bounce back up to row 0, and repeat.
Use an array of numRows StringBuilder objects. For each character, append it to the StringBuilder for its current row. Flip direction when you hit the top or bottom row.
This is the key optimization: Instead of a 2D grid with empty cells, we use just numRows strings. Each character goes directly into its row's string. No wasted space, no column tracking, no empty cells. Same O(n) time, but now O(n) space instead of O(n * numRows).
Let's trace through "PAYPALISHIRING" with numRows = 3, watching the direction bounce and each row's StringBuilder grow character by character.
| CHAR | ROW | DIR | ROW 0 | ROW 1 | ROW 2 |
|---|---|---|---|---|---|
| P | 0 | ↓ | P | ||
| A | 1 | ↓ | P | A | |
| Y | 2 | ↑ | P | A | Y |
| P | 1 | ↑ | P | AP | Y |
| A | 0 | ↓ | PA | AP | Y |
| L | 1 | ↓ | PA | APL | Y |
| I | 2 | ↑ | PA | APL | YI |
| S | 1 | ↑ | PA | APLS | YI |
| H | 0 | ↓ | PAH | APLS | YI |
| I | 1 | ↓ | PAH | APLSI | YI |
| R | 2 | ↑ | PAH | APLSI | YIR |
| I | 1 | ↑ | PAH | APLSII | YIR |
| N | 0 | ↓ | PAHN | APLSII | YIR |
| G | 1 | ↓ | PAHN | APLSIIG | YIR |
Notice the bounce: The direction flips whenever curRow hits 0 or numRows-1. This creates the zigzag pattern without ever needing to track columns. Each character lands in exactly the right row.
Several edge cases can short-circuit the algorithm entirely. Handle them upfront for clean code and early returns.
class Solution { public String convert(String s, int numRows) { // Edge cases: no zigzag needed if (numRows == 1 || numRows >= s.length()) return s; // Create one StringBuilder per row StringBuilder[] rows = new StringBuilder[numRows]; for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder(); int curRow = 0; boolean goingDown = false; // starts false, flips to true on row 0 for (char c : s.toCharArray()) { rows[curRow].append(c); // place char in current row // Bounce: flip direction at top and bottom if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown; // Move to next row curRow += goingDown ? 1 : -1; } // Concatenate all rows StringBuilder result = new StringBuilder(); for (StringBuilder row : rows) result.append(row); return result.toString(); } }
func convert(s string, numRows int) string { // Edge cases: no zigzag needed if numRows == 1 || numRows >= len(s) { return s } // Create one string builder per row rows := make([][]byte, numRows) curRow := 0 goingDown := false // starts false, flips to true on row 0 for i := 0; i < len(s); i++ { rows[curRow] = append(rows[curRow], s[i]) // place char in current row // Bounce: flip direction at top and bottom if curRow == 0 || curRow == numRows-1 { goingDown = !goingDown } // Move to next row if goingDown { curRow++ } else { curRow-- } } // Concatenate all rows var result []byte for _, row := range rows { result = append(result, row...) } return string(result) }
def convert(s: str, num_rows: int) -> str: # Edge cases: no zigzag needed if num_rows == 1 or num_rows >= len(s): return s # Create one list per row rows: list[list[str]] = [[] for _ in range(num_rows)] cur_row = 0 going_down = False # starts False, flips to True on row 0 for c in s: rows[cur_row].append(c) # place char in current row # Bounce: flip direction at top and bottom if cur_row == 0 or cur_row == num_rows - 1: going_down = not going_down # Move to next row cur_row += 1 if going_down else -1 # Concatenate all rows return "".join("".join(row) for row in rows)
impl Solution { pub fn convert(s: String, num_rows: i32) -> String { let num_rows = num_rows as usize; // Edge cases: no zigzag needed if num_rows == 1 || num_rows >= s.len() { return s; } // Create one Vec per row let mut rows: Vec<Vec<u8>> = vec![Vec::new(); num_rows]; let mut cur_row: i32 = 0; let mut going_down = false; // starts false, flips to true on row 0 for byte in s.bytes() { rows[cur_row as usize].push(byte); // place char in current row // Bounce: flip direction at top and bottom if cur_row == 0 || cur_row == num_rows as i32 - 1 { going_down = !going_down; } // Move to next row cur_row += if going_down { 1 } else { -1 }; } // Concatenate all rows rows.into_iter().flatten().collect::Vec<u8>() .into_iter().map(|b| b as char).collect() } }
function convert(s: string, numRows: number): string { // Edge cases: no zigzag needed if (numRows === 1 || numRows >= s.length) return s; // Create one string array per row const rows: string[] = Array.from({ length: numRows }, () => ""); let curRow = 0; let goingDown = false; // starts false, flips to true on row 0 for (const c of s) { rows[curRow] += c; // place char in current row // Bounce: flip direction at top and bottom if (curRow === 0 || curRow === numRows - 1) goingDown = !goingDown; // Move to next row curRow += goingDown ? 1 : -1; } // Concatenate all rows return rows.join(""); }
Why does goingDown start as false? Because the first character is at row 0 (a boundary). The if check immediately flips it to true, so the second character goes to row 1. This avoids an off-by-one error on the first iteration.
Enter a string and number of rows, then step through the algorithm watching the zigzag build character by character.
We iterate through the string exactly once, and each character is appended to its row's StringBuilder in O(1) amortized time. The final concatenation traverses all n characters once more, giving O(n) total time. The total space across all StringBuilder objects is exactly n characters (every character appears in exactly one row), plus O(numRows) overhead for the array of builders.
Each character is placed into a 2D matrix at its zigzag row and column, then the matrix is read row by row. The grid has numRows rows and up to n columns, but most cells are empty -- wasting O(n * numRows) memory for only n filled positions.
A single pass appends each character to its row's StringBuilder using a bouncing row counter. The direction flips at row 0 and row numRows-1, so each append is O(1) amortized. Total storage across all builders is exactly n characters -- no wasted empty cells.
The zigzag pattern repeats every 2 * (numRows - 1) characters, which means a formula-based approach can read characters directly by index without the bouncing loop. Both approaches are O(n) time, but the row builder avoids the wasted empty cells of a 2D grid. Since every character must be read and written at least once, O(n) time and O(n) space are both tight lower bounds.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.