Watch 10 video solutions for Zigzag Conversion, a medium level problem involving String. This walkthrough by NeetCode has 125,342 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N A P L S I I G Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I
Example 3:
Input: s = "A", numRows = 1 Output: "A"
Constraints:
1 <= s.length <= 1000s consists of English letters (lower-case and upper-case), ',' and '.'.1 <= numRows <= 1000Problem Overview: You receive a string and a number of rows. Write the characters in a zigzag pattern across the rows, then read the rows sequentially to form the final string. The challenge is reproducing the zigzag traversal efficiently without building a large 2D grid.
Approach 1: Direct Zigzag Simulation (O(n) time, O(n) space)
This method simulates how the zigzag is drawn. Create an array (or list) of strings representing each row. Iterate through the input string and append each character to the current row. Maintain a direction flag: move downward until the bottom row, then reverse direction and move upward until the top row. This mirrors the exact zigzag movement and is easy to implement. The algorithm touches each character once, giving O(n) time complexity, while storing rows requires O(n) additional space for the result.
The key insight is tracking row movement with a pointer and flipping direction at row boundaries. After processing all characters, concatenate all rows to produce the final string. This approach is straightforward and reliable, which makes it the most common solution used in interviews. The problem itself primarily involves string manipulation and careful index control.
Approach 2: Mathematical Index Calculation (O(n) time, O(1) extra space)
The zigzag pattern repeats every cycle = 2 * (numRows - 1) characters. Instead of simulating movement, compute which characters belong to each row based on this cycle. Iterate row by row. For each row, jump through the string in steps of the cycle length to collect vertical characters. Middle rows also include diagonal characters located at i + cycle - 2 * row. This pattern-based approach eliminates the need for row buffers.
The algorithm still processes each character at most once, resulting in O(n) time complexity. Extra memory usage is O(1) aside from the output string. This approach is slightly more complex but demonstrates deeper understanding of pattern repetition in string traversal and array-style indexing.
Recommended for interviews: Direct Zigzag Simulation is the expected solution in most coding interviews. It is simple, readable, and clearly models the zigzag behavior. The mathematical cycle approach is a strong follow-up optimization because it shows you recognized the repeating structure of the pattern. Explaining both approaches demonstrates both implementation skill and algorithmic insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Zigzag Simulation | O(n) | O(n) | Best general solution. Easy to implement and commonly expected in interviews. |
| Mathematical Index Calculation | O(n) | O(1) extra | Useful when you want a pattern-based traversal without maintaining row buffers. |