#6 Zigzag Conversion
the problem
In plain words
Write the string s in a zigzag over numRows rows: go straight down the first column, then climb diagonally up and to the right until you are back on the top row, then go straight down again, and keep going. Return the text you get by reading the rows from top to bottom, each one left to right.
in s = "PAYPALISHIRING", numRows = 3
out "PAHNAPLSIIGYIR"
Row 0 holds P A H N, row 1 holds A P L S I I G, row 2 holds Y I R.
in s = "PAYPALISHIRING", numRows = 4
out "PINALSIGYAHRPI"
Rows: P I N · A L S I G · Y A H R · P I.
in s = "A", numRows = 1
out "A"
- 1 ≤ s.length ≤ 1000
- s has English letters (both cases), ',' and '.'
- 1 ≤ numRows ≤ 1000
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSimulationMatrix traversal & in-place transforms
where this runsThe rail fence cipher, a classical transposition cipher, writes a message in exactly this zigzag over k rails and sends the rails one after another.
The columns of the picture don't matter, only the row of each character. That row goes 0, 1, …, numRows − 1 and back up, so one StringBuilder per row and a step that flips at the ends is enough.
solutions
From brute force to optimal
Build a numRows × n char grid, place each character where the picture puts it, then read the grid row by row.
- Go down a column; at the bottom row, move up and right one cell at a time.
- At the top row, go down again.
- Read every row left to right, skipping empty cells.
Reading the grid scans numRows × n cells, most of them empty.
The grid itself: up to 1000 × 1000 chars.
class Solution { public String convert(String s, int numRows) { if (numRows == 1) return s; int n = s.length(); char[][] grid = new char[numRows][n]; // never more than n columns int r = 0, c = 0; boolean down = true; for (int i = 0; i < n; i++) { grid[r][c] = s.charAt(i); if (r == 0) down = true; // top: go down else if (r == numRows - 1) down = false; // bottom: go up and to the right if (down) r++; else { r--; c++; } } StringBuilder out = new StringBuilder(n); for (char[] row : grid) for (char ch : row) if (ch != 0) out.append(ch); // '\0' marks an empty cell return out.toString(); }}Only the row matters. Walk the string with a row pointer that bounces between the top and bottom rows.
- If numRows == 1, return s.
- Append each char to rows[r]; at row 0 set step = +1, at the last row set step = −1; r += step.
- Join the rows in order.
Each character is appended twice: once to its row, once to the answer.
The row builders hold all n characters.
class Solution { public String convert(String s, int numRows) { if (numRows == 1) return s; StringBuilder[] rows = new StringBuilder[numRows]; for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder(); int r = 0, step = 1; for (char ch : s.toCharArray()) { rows[r].append(ch); if (r == 0) step = 1; // top row: head down else if (r == numRows - 1) step = -1; // bottom row: head up r += step; } StringBuilder out = new StringBuilder(s.length()); for (StringBuilder row : rows) out.append(row); return out.toString(); }}Dry run (row builders)
The pattern repeats every 2·numRows − 2 characters. For each row, jump through s and pick its characters directly.
- cycle = 2 · numRows − 2.
- Row r takes index start + r for start = 0, cycle, 2·cycle, …
- Middle rows also take start + cycle − r (the diagonal) when it exists.
Every character is appended exactly once.
Only counters besides the output builder.
class Solution { public String convert(String s, int numRows) { if (numRows == 1) return s; int n = s.length(), cycle = 2 * numRows - 2; // one trip down and back up StringBuilder out = new StringBuilder(n); for (int r = 0; r < numRows; r++) { for (int start = 0; start + r < n; start += cycle) { out.append(s.charAt(start + r)); // on the way down int up = start + cycle - r; // on the way back up (middle rows only) if (r > 0 && r < numRows - 1 && up < n) out.append(s.charAt(up)); } } return out.toString(); }}in the room
How to say it in the interview
talk track
- Point out that the picture's columns are a distraction: only each character's row matters.
- Code the row builders with a bouncing step, and handle numRows == 1 first.
- If asked for less memory, derive the cycle 2·numRows − 2 and jump through the string.
traps
- Forgetting numRows == 1: the step never flips and the row index runs off the end.
- Creating
new StringBuilder[numRows]and appending without filling it: every slot is null. - In the cycle version, adding the diagonal character for row 0 and the last row too — those rows have no diagonal.
what they ask next
Follow-ups
Undo it: given the zigzag text and numRows, recover s?
Count how many characters each row gets (walk the bouncing row pointer once), cut the text into those rows, then walk the zigzag again, taking the next character from row r each step.
What if numRows ≥ s.length()?
Each character gets its own row, read top to bottom, so the answer is s itself. The row-builder code already handles it.
before you submit
Edge cases to test
- numRows = 1 → s unchanged.
- numRows ≥ s.length() → s unchanged: one character per row.
- numRows = 2 → characters at even indices, then odd indices.
practise next
Similar problems
- #54Spiral MatrixMediumin Matrices
- #103Binary Tree Zigzag Level Order TraversalMediumin Traversals