Zigzag Conversion - Solution & Explanation
Problem Statement
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 <= 1000sconsists of English letters (lower-case and upper-case),','and'.'.1 <= numRows <= 1000
Approach Overview
Problem 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.
Approach 1: Direct Zigzag Simulation
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.
Complexity
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.
Approach 2: Mathematical Index Calculation
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.
Complexity
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 3: Simulation
We use a 2D array g to simulate the process of arranging the string in a zigzag pattern, where g[i][j] represents the character at row i and column j. Initially, i = 0. We also define a direction variable k, initially k = -1, which means moving upwards.
We traverse the string s from left to right. For each character c, we append it to g[i]. If i = 0 or i = numRows - 1, it means the current character is at a turning point in the zigzag pattern, so we reverse the value of k, i.e., k = -k. Then, we update i to i + k, which means moving up or down one row. Continue traversing the next character until the end of the string s. Finally, we return the concatenation of all rows in g as the result.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
C
PHP
Complexity Comparison
| 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. |
| Simulation | — |
Detailed Complexity Analysis
| 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 |
Video Solution
ZigZag Conversion - Leetcode 6 - Python • NeetCode • 166,321 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Zigzag Conversion easy or hard?
Zigzag Conversion Python/Java solution
How to solve Zigzag Conversion in O(n)?
What is the best approach for Zigzag Conversion?
Is Zigzag Conversion asked at Google/Amazon/Meta?
What data structure is used in Zigzag Conversion?
What is the time complexity of Zigzag Conversion?
Ready to solve this problem?
Practice Zigzag Conversion with our built-in code editor and test cases.
Practice on FleetCode