Zigzag Conversion — Solution in Python, Java & C++
Zigzag Conversion solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Zigzag Conversion is a medium coding problem on strings and simulation, asked in Amazon, Microsoft and Adobe interviews.
- Difficulty: Medium
- Topics: Strings, Simulation
- Asked at: Amazon, Microsoft, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Lay the characters of s out on numRows rows in a zigzag: the first character goes on row 0, then each next character goes one row lower until the bottom row is reached, then one row higher (moving one column right each step) until row 0 is reached again, and so on.
For s = "CODEKAIRO.ROCKS" and numRows = 3 the layout is:
C K O C
O E A R . O K
D I R S
Return the string obtained by reading the rows top to bottom, each row left to right. With a single row the text is unchanged.
Example 1
Input: s = "CODEKAIRO.ROCKS", numRows = 3
Output: "CKOCOEAR.OKDIRS"
Explanation: Rows read `CKOC`, `OEAR.OK` and `DIRS`.
Example 2
Input: s = "ZigZag,Fun", numRows = 4
Output: "Z,igFgauZn"
Example 3
Input: s = "A", numRows = 1
Output: "A"
Constraints
1 <= s.length <= 1000s consists of English letters, ',' and '.'1 <= numRows <= 1000
Hints for Zigzag Conversion
Hint 1
You do not need a 2-D grid: only the order of characters within each row matters.
Hint 2
The pattern repeats every
2 * numRows - 2characters (one trip down and back up).Hint 3
Row
rtakes indexjforj = r, r + cycle, …, and every middle row also takesj + cycle - 2rfrom the upward stroke.
How to solve Zigzag Conversion
The zigzag is periodic with period cycle = 2·numRows − 2, so every row can be read straight from s by index arithmetic instead of drawing the picture.
Approach
- If
numRowsis 1 or at leasts.length, returnsunchanged — no character ever moves. - Set
cycle = 2·numRows − 2. - For each row
rfrom 0 tonumRows − 1, walkj = r, r + cycle, r + 2·cycle, …whilej < nand appends[j]. - For a middle row (
0 < r < numRows − 1), afters[j]also appends[j + cycle − 2r]when that index exists — it is the character the upward diagonal drops on rowrwithin the same period.
Why it works
Within one period the column goes down through rows 0…numRows−1 (offsets 0…numRows−1) and back up through rows numRows−2…1 (offsets numRows…cycle−1). Row r therefore receives offset r on the way down and offset cycle − r on the way up, and the two coincide only for the top and bottom rows. Reading periods in order, and within a period the down offset before the up one, gives each row's characters left to right.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
numRows = 1makes the cycle 0 — handle it first or the loop never advances.- Top and bottom rows get one character per period, not two; adding the up-stroke there duplicates characters.
- Building an actual
numRows × ngrid works but wastes memory whennumRowsis large.
Reference solution
Python
def zigzagConvert(s: str, numRows: int) -> str:
n = len(s)
if numRows == 1 or numRows >= n:
return s
cycle = 2 * numRows - 2
out = []
for r in range(numRows):
j = r
while j < n:
out.append(s[j])
k = j + cycle - 2 * r
if 0 < r < numRows - 1 and k < n:
out.append(s[k])
j += cycle
return "".join(out)Java
public static String zigzagConvert(String s, int numRows) {
int n = s.length();
if (numRows == 1 || numRows >= n) return s;
int cycle = 2 * numRows - 2;
StringBuilder sb = new StringBuilder();
for (int r = 0; r < numRows; r++) {
for (int j = r; j < n; j += cycle) {
sb.append(s.charAt(j));
int k = j + cycle - 2 * r;
if (r > 0 && r < numRows - 1 && k < n) sb.append(s.charAt(k));
}
}
return sb.toString();
}C++
string zigzagConvert(string s, int numRows) {
int n = (int)s.size();
if (numRows == 1 || numRows >= n) return s;
int cycle = 2 * numRows - 2;
string out;
for (int r = 0; r < numRows; r++) {
for (int j = r; j < n; j += cycle) {
out.push_back(s[j]);
int k = j + cycle - 2 * r;
if (r > 0 && r < numRows - 1 && k < n) out.push_back(s[k]);
}
}
return out;
}JavaScript
var zigzagConvert = function(s, numRows) {
var n = s.length;
if (numRows === 1 || numRows >= n) return s;
var cycle = 2 * numRows - 2;
var out = [];
for (var r = 0; r < numRows; r++) {
for (var j = r; j < n; j += cycle) {
out.push(s[j]);
var k = j + cycle - 2 * r;
if (r > 0 && r < numRows - 1 && k < n) out.push(s[k]);
}
}
return out.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings