Zigzag Conversion LeetCode 6 Guide

LeetCode 6 Zigzag Conversion asks you to write a given string in a zigzag pattern across a specified number of rows, then read the result line by line from top to bottom. The output is the concatenation of all rows read left to right.

For example, "PAYPALISHIRING" written in a zigzag across 3 rows produces rows P-A-H-N, A-P-L-S-I-I-G, and Y-I-R. Reading those rows left to right gives "PAHNAPLSIIGYIR".

The problem is deceptively simple — the zigzag visual is easy to draw, but translating that visual into code requires a clean strategy for tracking which row each character belongs to.

The cleanest way to solve this problem is simulation. Create numRows empty string buckets — one per row. Iterate through each character in the input string, appending it to the bucket for the current row. Toggle direction when you hit the top row (row 0) or the bottom row (row numRows-1).

After processing all characters, join all the row buckets in order. The concatenation of row 0, row 1, ..., row numRows-1 is your answer. This approach requires no math about index positions and maps directly to the visual zigzag pattern.

The direction toggle is the key implementation detail. Start moving downward (direction = +1). When curRow reaches numRows-1, flip to -1. When curRow reaches 0, flip back to +1. Each character is appended to rows[curRow], then curRow += direction.

The algorithm is straightforward to implement once you understand the direction toggle. You need a list of numRows empty strings, a current row pointer starting at 0, and a direction variable starting at +1 (moving down).

For each character in the string, append it to the bucket at the current row, then update the direction if you are at the boundary rows, and finally advance the current row by the direction value.

Edge case: if numRows is 1, every character goes to row 0 and the output equals the input. Return s directly to avoid a divide-by-zero situation with the direction logic.

An alternative to simulation is to compute the output indices directly using math. Each full zigzag cycle has length cycleLen = 2 * numRows - 2. For row r, characters appear at positions cycleLen * k + r for each integer k, and also at cycleLen * k + (cycleLen - r) for interior rows (not the first or last row).

You iterate over each row from 0 to numRows-1, and for each row you collect all characters at the computed positions. This avoids building row buckets entirely and reads directly from the original string.

In practice the simulation approach is simpler to write correctly in an interview setting. The math approach has the same O(n) time complexity but O(1) extra space since you are not building intermediate row strings — you write directly to the output.

Let's trace the simulation for "PAYPALISHIRING" with numRows=3. We have three buckets: row0, row1, row2. The direction starts at +1 (going down). We visit each character in order and append it to the current row, toggling direction at the boundaries.

After processing all 14 characters: row 0 receives P, A, H, N → "PAHN". Row 1 receives A, P, L, S, I, I, G → "APLSIIG". Row 2 receives Y, I, R → "YIR". Joining gives "PAHNAPLSIIGYI R" — wait, correcting: "PAHN" + "APLSIIG" + "YIR" = "PAHNAPLSIIGYIR".

The direction toggle happens at positions: P(row0, flip to down), A(row1), Y(row2, flip to up), P(row1), A(row0, flip to down), L(row1), I(row2, flip to up), S(row1), H(row0, flip to down), I(row1), R(row2, flip to up), I(row1), N(row0, flip to down), G(row1). Result: "PAHNAPLSIIGYIR".

In Python: if numRows == 1 or numRows >= len(s): return s. Then rows = [""] * numRows, curRow = 0, goingDown = False. For each c in s: rows[curRow] += c; if curRow == 0 or curRow == numRows - 1: goingDown = not goingDown; curRow += 1 if goingDown else -1. Return "".join(rows). Time O(n), space O(n).

In Java: use StringBuilder[] rows = new StringBuilder[numRows], initialize each, then iterate with the same direction toggle logic. Append each char to rows[curRow]. Join with a StringBuilder at the end. The pattern is identical — only the syntax differs.

Both implementations run in O(n) time and O(n) space. The space is unavoidable because you are building the output string (the output itself is O(n)). If you count auxiliary space only, the simulation uses O(numRows) buckets which is at most O(n).

Zigzag Conversion belongs to a family of string rearrangement problems. Reverse Words in a String asks you to rearrange tokens rather than individual characters. String Compression requires in-place transformation using a write pointer. These all share the pattern of reading left-to-right and writing to a structured output.

Encode and Decode Strings is another close relative — it also involves transforming strings for a specific read-back pattern, relying on a schema rather than spatial arrangement. If you can implement Zigzag cleanly, these adjacent problems become much more approachable.

For interview preparation, group these string transformation problems together: Zigzag (LeetCode 6), Reverse Words (LeetCode 151), String Compression (LeetCode 443), and Determine if String Halves Are Alike (LeetCode 1704). Each reinforces the skill of tracking state while iterating through a string.