The Zigzag Conversion problem (LeetCode 6) asks us to write a string in a zigzag pattern across a given number of rows, and then read it row by row.
Visualizing Zigzag Movement
For numRows = 3: P A H N A P L S I I G Y I R
Each row follows a cyclic pattern. For row i, the next character index is determined by stepping down and up in the zigzag structure:
- Downward Step Size:
2 * (numRows - 1 - i) - Upward Step Size:
2 * i
C++ Solution
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
string convert(string s, int numRows) {
int n = s.size();
if (n == 1 || numRows < 2 || n <= numRows) return s;
string ans;
for (int i = 0; i < numRows; i++) {
int j = i;
ans.push_back(s[i]); // First character of the row
int down = 2 * (numRows - 1 - i); // Downward step size
int up = 2 * i; // Upward step size
while (j < n) {
j += down;
if (j < n && down > 0) ans.push_back(s[j]);
j += up;
if (j < n && up > 0) ans.push_back(s[j]);
}
}
return ans;
}
};
Complexity Analysis
- Time Complexity: $O(N)$ where $N$ is the length of the string. Every character is visited exactly once to construct the output string.
- Space Complexity: $O(1)$ auxiliary space if we do not count the output string.