6. Zigzag Conversion - Detailed Explanation
Problem Statement
Given a string s and an integer numRows, rearrange s into a zigzag pattern on numRows rows. The zigzag pattern means that you fill the first row left to right, then diagonally down to the last row, then diagonally up to the top row, and repeat until all characters are placed. Finally, read the zigzag pattern row by row to get the converted string.
-
Input: A string
sand an integernumRowsindicating the number of rows for the zigzag pattern. -
Output: A string representing the characters of
sread line by line from the zigzag pattern.
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Explanation: The string is arranged in 3 rows as follows (visualized in a fixed-width font):
P A H N
A P L S I I G
Y I R
Reading line by line gives "PAHNAPLSIIGYIR".
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation: Zigzag pattern in 4 rows:
P I N
A L S I G
Y A H R
P I
Reading line by line yields "PINALSIGYAHRPI".
Example 3:
Input: s = "ABCDEFG", numRows = 3
Output: "AEBDFCG"
Explanation: The zigzag pattern for 3 rows is:
A E (columns...)
B D F C
C G
Row by row, this becomes "AEBDFCG".
Constraints:
1 <= s.length <= 10001 <= numRows <= 1000sconsists of letters (upper and lower case) and may include punctuation like','or'.'.- If
numRows == 1ornumRows >= len(s), the zigzag pattern is just the original string (no zigzag needed).
Hints
-
Visualize the Zigzag: Imagine writing the string in a zigzag form across the given number of rows. Draw a grid of rows and place characters one by one: first go down each row, then reverse direction to go back up diagonally, and repeat. This visualization can guide your approach.
-
Simulate the Process: A straightforward way is to simulate filling the zigzag pattern. You can use an array (or list) of strings to represent each row and append characters to the appropriate row as you iterate through
s, switching direction when you reach the top or bottom. -
Pattern Observation: Notice that characters in the first and last rows follow a repeating interval. Characters in the middle rows appear twice in each full zigzag cycle: once on the way down and once on the way up. Identifying this cycle can lead to a direct calculation of indices.
-
Edge Case – Single Row: If
numRowsis 1, the output is justsitself (no zigzag occurs). Always handle this case explicitly to avoid unnecessary computation or errors in your logic.
Approach 1: Brute Force Simulation (Using a Matrix or Row Lists)
Idea: The brute force approach is to literally simulate the zigzag writing process. One way is to use a 2D matrix of size numRows x len(s) and fill it with characters in the correct positions, then read row by row. However, we can achieve the same result more efficiently by using a list of strings (or StringBuilder in Java) for each row and simulating the zigzag traversal.
Steps:
-
Initialize Data Structure: Create a list with
numRowsempty strings (for Python) or use an array of StringBuilder for Java. These will store characters for each row. -
Traverse the String: Use an index to track the current row (start at row 0) and a direction indicator (down or up). Iterate over each character
cins:- Append
cto the current row's string. - If you are at the top row (row 0), you need to start moving down. If at the bottom row (
numRows - 1), start moving up. Toggle the direction when you hit top or bottom. - Move to the next row in the current direction (if moving down,
row += 1; if moving up,row -= 1).
- Append
-
Combine Rows: After filling all characters, concatenate the strings from each row in order. This gives the final zigzag-converted string.
Using a matrix explicitly is straightforward but not memory-efficient. Instead, the above simulation uses O(n) extra space for the row strings, rather than O(n * numRows) for a full matrix. The logic remains the same: you're emulating writing in zigzag and reading across.
Example (Simulation):
Suppose s = "HELLO" and numRows = 3. We simulate the process:
- Start at
row = 0(top),direction = down. - Add
'H'to row0. (Rows:["H", "", ""]; now at row0, go down) - Add
'E'to row1. (Rows:["H", "E", ""]; now at row1, still going down) - Add
'L'to row2. (Rows:["H", "E", "L"]; reached bottom row2, toggle direction to up) - Add
'L'to row1. (Rows:["H", "EL", "L"]; now at row1, going up) - Add
'O'to row0. (Rows:["HO", "EL", "L"]; reached top row0, toggle direction to down, but string ended) - Concatenate rows:
"HO" + "EL" + "L" = "HOELL".
The result for "HELLO" with 3 rows is "HOELL", which matches the zigzag reading of the pattern:
H O
E L
L
This matches our simulation result.
Python Implementation (Brute Force Simulation):
In this code, we use a list of strings rows to accumulate characters for each row. The variable cur_row moves from 0 to numRows-1 and back, toggling direction when it hits 0 or numRows-1. Finally, we join all rows' strings to get the converted result.
Analysis: This brute force simulation runs in linear time relative to the length of the string. Each character is placed exactly once into a row, and then we combine the rows.
-
Time Complexity: O(n), where n is
len(s). We iterate through the string once and the concatenation of rows also takes O(n) total. (If we used an actual matrix of sizenumRows x n, filling it would be O(n) and reading it would be another O(n), still linear). -
Space Complexity: O(n), for storing the zigzag pattern in the worst case. We use additional space proportional to the length of the input for the rows list (not counting output storage). A full matrix approach would use O(n * numRows) space, but the optimized row-list approach uses O(n).
Approach 2: Optimal Solution (Direct Index Calculation)
Idea: The simulation above is already efficient (O(n) time), but we can derive a formula to directly determine the pattern. By analyzing the zigzag pattern, we find that characters follow a cycle. This approach calculates the index positions for each row without explicitly simulating the path, which can simplify the solution and avoid using extra data structures (just appending to the result string or StringBuilder).
Pattern Analysis:
In a zigzag of numRows, characters cycle down and up. For example, with numRows = 4, the pattern repeats every 2*numRows - 2 = 6 characters (this is the cycle length). Generally, the cycle length cycleLen = 2 * numRows - 2 (for numRows > 1). Within one cycle:
-
First row: characters appear at indices
0, cycleLen, 2*cycleLen, .... -
Last row (row
numRows-1): characters appear at indicesnumRows-1, numRows-1 + cycleLen, numRows-1 + 2*cycleLen, .... -
Middle rows: For row
i(0-indexed, not first or last), characters appear at two positions in each cycle:- At index
j = k*cycleLen + i(the downward stroke), and - At index
j2 = (k+1)*cycleLen - i(the upward stroke, coming back from the bottom) for each integerksuch that these indices are within bounds.
- At index
Let's break that down with an example. Consider s = "PAYPALISHIRING" and numRows = 4 (cycleLen = 6):
- Row 0 (first row): indices
0, 6, 12, ...→ characters:P, I, N, ... - Row 1: indices
1, 5, 7, 11, 13, ...→ characters:A, L, S, I, G, ... - Row 2: indices
2, 4, 8, 10, ...→ characters:Y, A, H, R, ... - Row 3 (last row): indices
3, 9, ...→ characters:P, I, ...
Reading in this way for each row yields the result "PINALSIGYAHRPI". We can use this pattern to construct the string without simulating every zigzag step.
Algorithm (Direct):
-
Handle the special case: if
numRows == 1, returns(no zigzag). -
Compute
cycleLen = 2 * numRows - 2. -
Initialize an empty result string (or StringBuilder for efficiency in Java).
-
Loop
rfrom0tonumRows-1(for each row in the zigzag):- For each cycle index
kstarting from0, compute the index of the character in this row for the k-th cycle asi = k * cycleLen + r. Ifiis beyond the string length, break out of the loop for this row. - Append
s[i]to the result. - Middle rows: If
ris not 0 and notnumRows-1, there is a second character in the cycle for this row: indexj2 = (k+1)*cycleLen - r. (This formula comes from the symmetry of the zigzag: the character that appears on the "upward" diagonal for rowr.) Ifj2is within bounds, appends[j2]as well.
- For each cycle index
-
Continue until you’ve processed all rows. The result string constructed will be the zigzag conversion.
This approach uses arithmetic to skip directly to the characters of each row. It might appear complex at first, but it's efficient and avoids the overhead of tracking direction or using additional lists.
Example (Direct Calculation):
Using the same example s = "PAYPALISHIRING", numRows = 3 (here cycleLen = 2*3-2 = 4):
- Row 0: take indices
0, 4, 8, 12, ...→P, A, H, N - Row 1: take indices
1, 3, 5, 7, 9, 11, 13, ...→A, P, L, S, I, I, G - Row 2: take indices
2, 6, 10, ...→Y, I, RCombine:"PAHN" + "APLSIIG" + "YIR" = "PAHNAPLSIIGYIR". We get the same output as expected.
Optimal Complexity: This method still processes each character exactly once, so:
-
Time Complexity: O(n), where n is the length of the string. We visit each character in the string exactly one time during the index calculations (two times in the worst case of middle rows, but overall proportional to n).
-
Space Complexity: O(n) for the output. The algorithm itself uses only a few extra variables (O(1) auxiliary space), so if we don't count the output string, additional space is constant. In terms of total space including output, it's O(n).
Code Implementations
Python
Java
Both implementations handle the zigzag conversion. The Python version builds the result in a list of characters for efficiency and then joins, while the Java version uses a StringBuilder. Both follow the optimized approach of calculating positions based on the cycle length. You can test with the given examples or your own strings to verify the output.
Step-by-Step Walkthrough of the Zigzag Process
Let's walk through a concrete example in detail to see how the zigzag pattern is formed. Consider the input s = "PAYPALISHIRING" with numRows = 4. We will simulate the zigzag placement and see how the result is built:
We have 4 rows, so imagine 4 horizontal rows where characters will be placed. We'll trace the path of filling these rows:
-
Start at Row 0 (top).
- Place
'P'(index 0 of string) in row 0. - Move down to the next row.
- Place
-
Row 1:
- Place
'A'(index 1) in row 1. - Move down to the next row.
- Place
-
Row 2:
- Place
'Y'(index 2) in row 2. - Move down to the next row.
- Place
-
Row 3 (bottom):
- Place
'P'(index 3) in row 3. - Change direction: we reached the bottom row, so we will start moving upwards on the next character.
- Move up to the next row (which is row 2).
- Place
-
Row 2 (moving up):
- Place
'A'(index 4) in row 2. (Notice we're now filling row 2 again on the way up.) - Move up to the next row (row 1).
- Place
-
Row 1:
- Place
'L'(index 5) in row 1. - Move up to the next row.
- Place
-
Row 0 (top):
- Place
'I'(index 6) in row 0. - Change direction: reached the top, so turn to go downwards next.
- Move down to row 1.
- Place
-
Row 1 (downwards again):
- Place
'S'(index 7) in row 1. - Move down to row 2.
- Place
-
Row 2:
- Place
'H'(index 8) in row 2. - Move down to row 3.
- Place
-
Row 3 (bottom):
- Place
'I'(index 9) in row 3. - Change direction to upwards.
- Move up to row 2.
- Place
-
Row 2 (upwards):
- Place
'R'(index 10) in row 2. - Move up to row 1.
- Place
-
Row 1:
- Place
'I'(index 11) in row 1. - Move up to row 0.
- Place
-
Row 0 (top):
- Place
'N'(index 12) in row 0. - Change direction to downwards.
- Move down to row 1.
- Place
-
Row 1:
- Place
'G'(index 13) in row 1. - Move down (would go to row 2, but we've placed all characters).
- Place
Now let's see the content of each row after placing all characters:
- Row 0 contains: P I N (characters at indices 0, 6, 12)
- Row 1 contains: A L S I G (indices 1, 5, 7, 11, 13)
- Row 2 contains: Y A H R (indices 2, 4, 8, 10)
- Row 3 contains: P I (indices 3, 9)
If we read these rows left to right, line by line, we get:
Row 0: P I N
Row 1: A L S I G
Row 2: Y A H R
Row 3: P I
Concatenating them: "PINALSIGYAHRPI", which matches the expected output for this example.
This step-by-step illustrates how the zigzag pattern is constructed by moving down and up the rows. Each time we hit the bottom or top, we reverse direction. The process continues until all characters are placed in their appropriate row positions.
Complexity Analysis
We will analyze both approaches discussed in terms of time and space complexity:
-
Brute Force Simulation (Approach 1): We iterate over each character once to place it in the appropriate row, and then join the rows. This results in O(n) time complexity (n = length of the string). Space complexity is O(n) to store the characters in the row lists (in addition to the output). If a full matrix were used, space would be O(n * numRows), but the optimized simulation only uses O(n). In our example with
s.length = 14andnumRows = 4, this approach handles 14 characters in a single pass. -
Direct Index Calculation (Approach 2): We determine positions of characters row by row. We still visit each character exactly once overall, so the time complexity is O(n). The space complexity is O(n) for the output string. This approach uses O(1) extra space aside from the output (just counters and indices). Both approaches are efficient for the given constraints (even for the maximum
1000 x 1000case, which at most handles 1,000,000 characters operations, well within modern computing capabilities).
In summary, both the simulation and the direct calculation methods achieve linear time complexity. The primary difference is in implementation clarity and constant factors, not in big-O order. The direct approach avoids additional data structures for rows, while the simulation approach might be easier to understand.
Common Mistakes and Edge Cases
-
Forgetting the Single Row Case: A very common mistake is not handling
numRows = 1. In this case, the zigzag conversion should return the original string without change. If not handled, the logic that toggles direction may break (for example, the cycle length formula would be2*1-2 = 0, which is problematic). Always include a check fornumRows <= 1(or equivalentlynumRows == 1) to directly return the input string. -
Off-by-One Errors in Direction Change: When simulating the zigzag, it's easy to flip direction at the wrong time. Remember that you should flip direction only when you have just placed a character in the top row (then turn downward) or in the bottom row (then turn upward). Missing this condition or flipping one step too late/early can scramble the pattern.
-
Incorrect Cycle Calculation: For the direct approach, calculating the index for the second character in the middle rows can be tricky. A mistake in the formula
j = i + cycleLen - 2*r(or its derivation) will lead to wrong placements. Ensure that for each middle row, you correctly identify the "zigzag partner" index in each cycle. -
Concatenating Strings Inefficiently: In some languages (like Python), building the result by doing
result += charin a loop can be inefficient due to string immutability (leading to O(n^2) time in worst case). It's better to use a list of characters andjoin, or in Java, use aStringBuilder. This isn't a logical bug but can cause timeouts for large inputs. -
Edge Case – Very Short Strings or Many Rows: If
shas length 0 or 1 (trivial cases) or ifnumRowsis greater than or equal tolen(s), the output should just bes(because either there's nothing to zigzag, or each character would occupy its own row with no zigzag needed). Make sure your solution gracefully handles these cases without error. For instance, ifs = "AB"andnumRows = 5, the result is"AB"(not an error or something else).
By keeping these pitfalls in mind, you can avoid common errors. Testing on edge cases like numRows = 1, numRows very large (relative to string length), and very short strings (like length 1 or 2) will help validate the correctness of the solution.
Alternative Variations of the Problem
The zigzag conversion described here is essentially writing a string in a zigzag (also known as the Rail Fence Cipher encoding). Some variations or related challenges include:
-
Decoding a Zigzag (Rail Fence) Cipher: Given a zigzag-converted string and the number of rows, reconstruct the original string. This is like the reverse of what we did, and one would have to figure out how the characters were distributed among rows to invert the process.
-
Zigzag Pattern Printing: Instead of returning a string, a problem might ask you to output the zigzag pattern in a matrix form or print it directly to the console. This would involve actually arranging characters (and perhaps filling blanks) to display the zigzag shape.
-
Diagonal Zigzag in Matrices: There are problems where you traverse a matrix in a zigzag or diagonal order. While the context is different (2D array instead of a single string), the idea of switching direction in a zigzag manner is similar.
-
Generalized Zigzag Join of Multiple Lists: In some scenarios, you might merge multiple sequences in a zigzag fashion (e.g., take one element from each list in order, then reverse the order, etc.). The concept of zigzag traversal can be extended to other data structures like multiple arrays or tree levels.
These variations require understanding the zigzag pattern concept and applying it in different contexts. The core logic of switching direction after reaching a boundary is a common thread.
Related Problems for Practice
Once you are comfortable with Zigzag Conversion, you might want to try these related problems to reinforce similar skills:
-
Binary Tree Zigzag Level Order Traversal (LeetCode 103): Traverse a binary tree in zigzag level order (alternate between left-to-right and right-to-left at each level). This involves a similar idea of reversing direction on each level, albeit in a tree structure.
-
Diagonal Traverse of a Matrix (LeetCode 498): Given a 2D matrix, return all elements in a diagonal zigzag order. This problem has you switch direction (down-right vs up-left) when hitting boundaries, analogous to zigzag logic.
-
Spiral Matrix (LeetCode 54): Although the pattern here is spiral, not zigzag, it is another example of a problem where simulating a path (and turning at boundaries) is key to collecting results.
-
Wave Array (GfG variant): Rearrange an array in alternating high-low form (e.g.,
[1,2,3,4]->[2,1,4,3]). It’s not a zigzag in two dimensions, but the idea of alternating pattern (up-down sequence) is conceptually similar. -
Rail Fence Cipher Encoding/Decoding: As mentioned, the zigzag conversion is basically the Rail Fence cipher. If you're interested in cryptography, implementing the encoding (which we've done here) and decoding of that cipher is a good exercise.
GET YOUR FREE
Coding Questions Catalog
