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.
This approach involves simulating the zigzag pattern by using an array of strings to represent each row. We iterate through the string, placing each character in the appropriate row based on the current direction (down or up in the zigzag pattern). We change the direction whenever we hit the top or bottom row.
The C solution implements a zigzag pattern simulation by creating an array of strings for each row. As we iterate through the input string, we add characters to the respective row. When we reach the top or bottom, we reverse direction. Finally, we concatenate all rows to produce the result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n represents the length of the input string, as we iterate through the string once.
Space Complexity: O(n), to store the zigzag rows.
This approach calculates the regular intervals for placing characters in the zigzag pattern without simulating the full grid. By deducing the mathematical relation of indices, characters are stored directly in the result string.
This C solution calculates the correct indices for zigzag order dynamically. By understanding the repetitive cycle length, it extracts characters directly in order. The outer loop runs over each row index, and within it, character indices are calculated for the zigzag transformation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the input string length, owing to a complete pass through the characters.
Space Complexity: O(n), needed for the output string.
| Approach | Complexity |
|---|---|
| Direct Zigzag Simulation | Time Complexity: O(n), where n represents the length of the input string, as we iterate through the string once. |
| Mathematical Index Calculation | Time Complexity: O(n), where n is the input string length, owing to a complete pass through the characters. |
| 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. |
ZigZag Conversion - Leetcode 6 - Python • NeetCode • 125,342 views views
Watch 9 more video solutions →Practice Zigzag Conversion with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor