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 are given a string and a number of rows. Write the characters in a zigzag pattern across those rows, then read the rows sequentially to produce the final string. The challenge is correctly mapping characters to their zigzag positions without explicitly building a 2D grid.
Approach 1: Direct Zigzag Simulation (O(n) time, O(n) space)
This approach simulates the zigzag writing process row by row. Create an array (or list) of strings representing each row. Iterate through the characters of the input string and append each character to the current row. Maintain a direction flag that moves the pointer either down or up through the rows. When the pointer reaches the first or last row, flip the direction. After processing all characters, concatenate the rows to build the final string. The algorithm touches each character exactly once, giving O(n) time complexity and O(n) extra space for storing row strings. This approach is easy to implement and mirrors the visual zigzag pattern directly. It’s commonly used when solving string transformation problems.
Approach 2: Mathematical Index Calculation (O(n) time, O(1) extra space)
The zigzag pattern follows a repeating cycle. For numRows = r, one full cycle length is cycle = 2 * (r - 1). Characters in the first and last rows appear every cycle positions. For middle rows, characters appear twice in each cycle: once vertically and once diagonally. Iterate row by row and compute indices directly using this cycle pattern. For each base index i, append s[i + row] and, for middle rows, also append s[i + cycle - row] if it exists. This avoids maintaining row buffers and relies on predictable index jumps derived from the zigzag structure. Time complexity remains O(n) because each character is processed once. Extra space can be O(1) aside from the output string. This technique relies on pattern recognition and basic math observations applied to a string.
Recommended for interviews: The direct zigzag simulation is usually the expected answer in interviews. It demonstrates clear reasoning, correct state transitions, and clean string manipulation. The mathematical index method is slightly more optimized in memory and shows deeper pattern recognition, but it’s easier to make indexing mistakes. Showing the simulation first proves you understand the zigzag structure, while deriving the cycle formula highlights stronger 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.
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.
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 for interviews and readability; mirrors the zigzag writing process directly |
| Mathematical Index Calculation | O(n) | O(1) | When you want constant extra space and can derive the repeating zigzag cycle |
ZigZag Conversion - Leetcode 6 - Python • NeetCode • 159,133 views views
Watch 9 more video solutions →Practice Zigzag Conversion with our built-in code editor and test cases.
Practice on FleetCode