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 <= 1000The key idea in Zigzag Conversion is to simulate how characters are placed when written in a zigzag pattern across multiple rows. Instead of actually drawing the zigzag grid, an efficient approach is to maintain a list of rows and append characters as you move down and up diagonally through the rows. A direction flag helps switch movement when the top or bottom row is reached.
For each character in the input string, add it to the current row and update the row index depending on the direction of traversal. After processing all characters, concatenate the rows to produce the final string. This approach avoids building a full 2D matrix and keeps memory usage minimal.
The algorithm processes each character once, leading to a time complexity of O(n), where n is the length of the string. The extra space required is also O(n) to store the row-wise results before combining them.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Row Simulation using Array of Strings | O(n) | O(n) |
| Cycle Pattern Observation | O(n) | O(1) to O(n) depending on implementation |
NeetCode
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.
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.
1public class Solution {
2 public string Convert(string s, int numRows) {
3 if (numRows == 1 || numRows >= s.Length) return s;
4 StringBuilder[] rows = new StringBuilder[numRows];
5 for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
6 int currentRow = 0;
7 bool goingDown = false;
8 foreach (char c in s) {
9 rows[currentRow].Append(c);
10 if (currentRow == 0 || currentRow == numRows - 1) goingDown = !goingDown;
11 currentRow += goingDown ? 1 : -1;
12 }
13 StringBuilder result = new StringBuilder();
foreach (StringBuilder row in rows) result.Append(row);
return result.ToString();
}
}The C# implementation uses an array of StringBuilders to simulate the zigzag traversal. The position of each character is managed by an index reflecting the current row, changing direction at the boundaries, and assembling the final string from all row strings.
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.
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.
1 public string Convert(string s, int numRows) {
if (numRows == 1) return s;
StringBuilder result = new StringBuilder();
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < s.Length; j += cycleLen) {
result.Append(s[j + i]);
if (i != 0 && i != numRows - 1 && j + cycleLen - i < s.Length)
result.Append(s[j + cycleLen - i]);
}
}
return result.ToString();
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Zigzag Conversion is a well-known medium-level string problem often used in technical interviews. It tests pattern recognition, indexing logic, and efficient string manipulation.
The zigzag pattern repeats in cycles of length 2 × (numRows − 1). Recognizing this pattern helps derive optimized solutions that calculate character positions mathematically instead of simulating movement.
A list or array of strings (or string builders) works best to represent each row of the zigzag pattern. This allows efficient appending as characters are processed sequentially.
The optimal approach simulates the zigzag traversal using an array of rows. You append characters while moving down and then diagonally up between rows. After processing the string, concatenating all rows produces the final result in O(n) time.
C# uses index calculation to extract the necessary characters from the input string, correlating directly with row numbers and cycling through the sequence, efficiently constructing the output.