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.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5char* convert(char* s, int numRowsThe 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.
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#
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.
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.