Zigzag Conversion
Zigzag Conversion is a medium arrays & hashing problem solved with the simulation pattern.
The best approach, optimal (one buffer per row), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (draw the zigzag on a grid) up.
Problem
Write the characters of a string s in a zigzag over numRows rows: go straight down from row 0 to row numRows - 1, then diagonally back up to row 0, then down again, and so on, one character per position. For example, "ALGORITHMS" on 3 rows looks like this:
A R M
L O I H S
G T
Return the string you get by reading the zigzag row by row, left to right (here "ARMLOIHSGT").
Examples
Example 1
- Input
s = "ALGORITHMS", numRows = 3- Output
"ARMLOIHSGT"- Why
- Written in a zigzag the rows are A, R, M (row 0), L, O, I, H, S (row 1) and G, T (row 2). Reading row by row gives ARM + LOIHS + GT.
Example 2
- Input
s = "WAVELENGTH", numRows = 4- Output
"WNAEGVLTEH"- Why
- Row 0 gets W, N; row 1 gets A, E, G; row 2 gets V, L, T; row 3 gets E, H.
Example 3
- Input
s = "OK", numRows = 5- Output
"OK"- Why
- With more rows than characters, each character sits on its own row and the order does not change.
Constraints
1 <= s.length <= 10001 <= numRows <= 1000scontains English letters (both cases),,and..
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (draw the zigzag on a grid) | O(numRows · n) | O(numRows · n) |
| Optimal (one buffer per row) | O(n) | O(n) |
1Brute force (draw the zigzag on a grid)
O(numRows · n)The final scan reads every cell of the grid.O(numRows · n)The grid has numRows rows and up to n columns.Place the characters on a 2D grid exactly as they would be drawn: go straight down a column, then diagonally up and to the right, and repeat. Then read the grid row by row, skipping empty cells.
- If numRows == 1, return s.
- grid = numRows × n cells; r = 0, c = 0, goingDown = true.
- For each char: grid[r][c] = char. If goingDown and r == numRows - 1, switch to going up; if going up and r == 0, switch to going down. Moving down: r++; moving up: r--, c++.
- Concatenate non-empty cells row by row.
class Solution {
public String convert(String s, int numRows) {
int n = s.length();
if (numRows == 1 || numRows >= n) return s;
char[][] grid = new char[numRows][n];
int r = 0, c = 0;
boolean down = true;
for (int i = 0; i < n; i++) {
grid[r][c] = s.charAt(i);
if (down && r == numRows - 1) down = false;
else if (!down && r == 0) down = true;
if (down) r++;
else { r--; c++; }
}
StringBuilder sb = new StringBuilder();
for (char[] row : grid)
for (char ch : row)
if (ch != 0) sb.append(ch);
return sb.toString();
}
}class Solution:
def convert(self, s: str, numRows: int) -> str:
n = len(s)
if numRows == 1 or numRows >= n:
return s
grid = [[''] * n for _ in range(numRows)]
r = c = 0
down = True
for ch in s:
grid[r][c] = ch
if down and r == numRows - 1:
down = False
elif not down and r == 0:
down = True
if down:
r += 1
else:
r -= 1
c += 1
return "".join(ch for row in grid for ch in row if ch)class Solution {
public:
string convert(string s, int numRows) {
int n = s.size();
if (numRows == 1 || numRows >= n) return s;
vector<vector<char>> grid(numRows, vector<char>(n, 0));
int r = 0, c = 0;
bool down = true;
for (char ch : s) {
grid[r][c] = ch;
if (down && r == numRows - 1) down = false;
else if (!down && r == 0) down = true;
if (down) r++;
else { r--; c++; }
}
string out;
for (auto& row : grid)
for (char ch : row)
if (ch != 0) out.push_back(ch);
return out;
}
};function convert(s, numRows) {
const n = s.length;
if (numRows === 1 || numRows >= n) return s;
const grid = Array.from({ length: numRows }, () => new Array(n).fill(""));
let r = 0, c = 0, down = true;
for (const ch of s) {
grid[r][c] = ch;
if (down && r === numRows - 1) down = false;
else if (!down && r === 0) down = true;
if (down) r++;
else { r--; c++; }
}
let out = "";
for (const row of grid)
for (const ch of row)
if (ch !== "") out += ch;
return out;
}2Optimal (one buffer per row)
O(n)Each character is appended once and copied once into the result.O(n)The row buffers together hold n characters.Columns do not matter for the answer, only which row each character lands on. Keep a string buffer per row and a current row that bounces between 0 and numRows - 1; append each character to its row's buffer and finally join the buffers.
- If numRows == 1 or numRows >= n, return s.
- rows = numRows empty buffers; row = 0, step = 1.
- For each char: append to rows[row]; if row == 0 set step = 1, if row == numRows - 1 set step = -1; row += step.
- Join all buffers in order.
class Solution {
public String convert(String s, int numRows) {
int n = s.length();
if (numRows == 1 || numRows >= n) return s;
StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
int row = 0, step = 1;
for (int i = 0; i < n; i++) {
rows[row].append(s.charAt(i));
if (row == 0) step = 1;
else if (row == numRows - 1) step = -1;
row += step;
}
StringBuilder out = new StringBuilder();
for (StringBuilder sb : rows) out.append(sb);
return out.toString();
}
}class Solution:
def convert(self, s: str, numRows: int) -> str:
n = len(s)
if numRows == 1 or numRows >= n:
return s
rows = [[] for _ in range(numRows)]
row, step = 0, 1
for ch in s:
rows[row].append(ch)
if row == 0:
step = 1
elif row == numRows - 1:
step = -1
row += step
return "".join("".join(r) for r in rows)class Solution {
public:
string convert(string s, int numRows) {
int n = s.size();
if (numRows == 1 || numRows >= n) return s;
vector<string> rows(numRows);
int row = 0, step = 1;
for (char ch : s) {
rows[row].push_back(ch);
if (row == 0) step = 1;
else if (row == numRows - 1) step = -1;
row += step;
}
string out;
for (auto& r : rows) out += r;
return out;
}
};function convert(s, numRows) {
const n = s.length;
if (numRows === 1 || numRows >= n) return s;
const rows = Array.from({ length: numRows }, () => []);
let row = 0, step = 1;
for (const ch of s) {
rows[row].push(ch);
if (row === 0) step = 1;
else if (row === numRows - 1) step = -1;
row += step;
}
return rows.map((r) => r.join("")).join("");
}Edge cases to test
- numRows = 1: the string is unchanged (there is no bouncing)
- numRows >= s.length: the string is unchanged
- numRows = 2: characters alternate between the two rows
Hints
Hint 1
Simulate it: walk down the rows, then back up, placing one character per step. When do you change direction?
Hint 2
You never need the column positions. Keep one buffer per row and append each character to the row you are currently on.
FAQ
What is the best time complexity for Zigzag Conversion?
Optimal (one buffer per row) runs in O(n) time and O(n) extra space. Each character is appended once and copied once into the result.
Which pattern does Zigzag Conversion use?
It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, Integer to English Words, String to Integer (atoi).
Is there a brute force solution for Zigzag Conversion?
Yes. Brute force (draw the zigzag on a grid) takes O(numRows · n) time and O(numRows · n) space. Place the characters on a 2D grid exactly as they would be drawn: go straight down a column, then diagonally up and to the right, and repeat.
Which edge cases should I test for Zigzag Conversion?
numRows = 1: the string is unchanged (there is no bouncing); numRows = s.length: the string is unchanged; numRows = 2: characters alternate between the two rows.