Log inSign up
mediumleetcodeNot Started

Zigzag Conversion

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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 · Example:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Explanation: Characters are distributed into 3 rows and concatenated row-wise.

Example 2 · Example:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation: Row 0: P I N Row 1: A L S I G Row 2: Y A H R Row 3: P I Result: "PINALSIGYAHRPI".

Example 3 · Example:

Input: s = "A", numRows = 1
Output: "A"
Explanation: Single row returns string unchanged.

Constraints:

  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Compute period/cycle lengths for alternating waveforms.
  • Formulate mathematical jump offsets for grid diagonals.
  • Eliminate intermediate string buffer allocations.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Zigzag or serpentine grid traversal.
  • Matrix writing in non-linear path with linear row extraction.

Algorithmic Decision Tree:

  • Row Simulation Oscillating Direction
  • Arithmetic Index Jumping

Connected Patterns:

Spiral MatrixDiagonal TraverseTranspose Matrix

1. 2D Character Grid Simulation

Intuition

Create a 2D matrix of size numRows x N. Place characters moving down vertically, then diagonally up-right. Concatenate all non-empty characters row by row.

When to apply: Basic visual grid simulation.

Algorithm

  1. If numRows == 1 || numRows >= s.length: return s.
  2. Create 2D grid filled with null characters.
  3. Simulate filling characters moving down and diagonally up.
  4. Collect characters row by row.
  5. Return result string.

2D Character Grid Simulation

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [P, A, Y, P, A, L, I, S, H, I, R, I, N, G]
Current operationSTEP 1 OF 6
Observation: In a 2D matrix of 3 rows, fill vertically downward
Visual state
Values and pointers at this exact step
array
S
P
A
Y
P
A
L
I
S
H
I
R
I
N
G
0
↑ COL 0 DOWN: 'P','A','Y'
1
2
3
4
5
6
7
8
9
10
11
12
13
Variables at this step
r
2
c
0
dir
UP_RIGHT
Check / comparison
Move downward: grid[0][0]='P', grid[1][0]='A', grid[2][0]='Y'.
Decision / next transition
Bottom row (2) reached. Reverse direction: move diagonally up-right.
Why this step matters

Observation: In a 2D matrix of 3 rows, fill vertically downward.

Decision: Place 'P' at row 0, 'A' at row 1, 'Y' at row 2 in column 0. Turn diagonally up-right.

Invariant: Downward motion populates rows 0 -> numRows - 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string convert(std::string s, int numRows) {
8 if (numRows == 1 || numRows >= (int)s.size()) return s;
9 int n = s.size();
10 std::vector<std::vector<char>> grid(numRows, std::vector<char>(n, 0));
11
12 int r = 0, c = 0, dir = 1;
13 for (char ch : s) {
14 grid[r][c] = ch;
15 if (r == 0) dir = 1;
16 else if (r == numRows - 1) dir = -1;
17
18 if (dir == 1) {
19 r++;
20 } else {
21 r--;
22 c++;
23 }
24 }
25
26 std::string res = "";
27 for (int i = 0; i < numRows; ++i) {
28 for (int j = 0; j <= c; ++j) {
29 if (grid[i][j] != 0) res += grid[i][j];
30 }
31 }
32 return res;
33 }
34};
35
36int main() {
37 Solution sol;
38 std::cout << sol.convert("PAYPALISHIRING", 3) << std::endl; // PAHNAPLSIIGYIR
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(numRows * N) — Grid traversal visits cells across the 2D matrix.
  • Space complexity: O(numRows * N)

Why Brute Force Doesn't Scale:

Linear arithmetic index jumping produces the output string in a single allocation.

Strict O(1) auxiliary space.

2. Row String Buffers Simulation

Intuition

Create an array of numRows strings. Start at currRow = 0, goingDown = false. For each character: append to rows[currRow]. If currRow == 0 || currRow == numRows - 1, flip goingDown = !goingDown. Move currRow += goingDown ? 1 : -1. Concatenate all rows.

When to apply: The standard intuitive solution.

Algorithm

  1. If numRows == 1 || numRows >= s.length: return s.
  2. Initialize rows = Array(numRows).fill(''), currRow = 0, goingDown = false.
  3. For c in s:
  4. rows[currRow] += c.
  5. If currRow == 0 || currRow == numRows - 1: goingDown = !goingDown.
  6. currRow += goingDown ? 1 : -1.
  7. Join and return rows.join('').

Row String Buffers Simulation

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [P, A, Y, P, A, L, I, S, H, I, R, I, N, G]
Current operationSTEP 1 OF 6
Observation: Instead of a sparse 2D grid, maintain 3 string builders
Visual state
Values and pointers at this exact step
array
S
P
A
Y
P
A
L
I
S
H
I
R
I
N
G
0
↑ ROW 0: 'P'
1
2
3
4
5
6
7
8
9
10
11
12
13
Variables at this step
curRow
1
goingDown
true
rows
["P","",""]
Check / comparison
Allocate rows = ['', '', '']. curRow = 0, goingDown = true.
Decision / next transition
Append 'P' to rows[0]. curRow becomes 1.
Why this step matters

Observation: Instead of a sparse 2D grid, maintain 3 string builders.

Decision: Append 'P' to rows[0]. Move down to curRow = 1.

Invariant: Compacting rows into 1D builders eliminates matrix space overhead.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string convert(std::string s, int numRows) {
8 if (numRows == 1 || numRows >= (int)s.size()) return s;
9 std::vector<std::string> rows(std::min(numRows, (int)s.size()));
10 int currRow = 0;
11 bool goingDown = false;
12
13 for (char c : s) {
14 rows[currRow] += c;
15 if (currRow == 0 || currRow == numRows - 1) {
16 goingDown = !goingDown;
17 }
18 currRow += goingDown ? 1 : -1;
19 }
20
21 std::string res;
22 for (const auto& row : rows) res += row;
23 return res;
24 }
25};
26
27int main() {
28 Solution sol;
29 std::cout << sol.convert("PAYPALISHIRING", 3) << std::endl; // PAHNAPLSIIGYIR
30 std::cout << sol.convert("PAYPALISHIRING", 4) << std::endl; // PINALSIGYAHRPI
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass over characters and simple string joins.
  • Space complexity: O(N)

3. Direct Math Index Jumping (Optimal O(1) Space)

Intuition

The period of the zigzag cycle is cycleLen = 2 * numRows - 2. For row r = 0 and row r = numRows - 1, characters appear at j = r, r + cycleLen, r + 2 * cycleLen, .... For middle rows 0 < r < numRows - 1, each cycle contains two characters: the vertical character at j and the diagonal character at j + cycleLen - 2 * r.

When to apply: The standard gold standard solution for zero auxiliary memory allocations.

Algorithm

  1. If numRows == 1 || numRows >= s.length: return s.
  2. cycleLen = 2 * numRows - 2, initialize res = "".
  3. For r from 0 to numRows - 1:
  4. For j from r to n - 1 stepping by cycleLen:
  5. res += s[j].
  6. If r > 0 && r < numRows - 1:
  7. diag = j + cycleLen - 2 * r.
  8. If diag < n: res += s[diag].
  9. Return res.

Direction-Alternating Row Bucket Simulation

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [P, A, Y, P, A, L, I, S, H, I, R, I, N, G]
Current operationSTEP 1 OF 6
Observation: Initialize 3 row buffers
Visual state
Values and pointers at this exact step
array
S
P
A
Y
P
0
↑ Append 'P' to Row 0
1
2
3
Variables at this step
curRow
0
goingDown
true
rows
{"0":"P","1":"","2":""}
Why this step matters

Observation: Initialize 3 row buffers. First character 'P' goes into Row 0.

Decision: Direction is down (step = +1). Next row is Row 1.

Invariant: Direction reverses at top (0) and bottom (numRows - 1) rows.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 std::string convert(std::string s, int numRows) {
7 if (numRows == 1 || numRows >= (int)s.size()) return s;
8
9 std::string res;
10 int n = s.size();
11 int cycleLen = 2 * numRows - 2;
12
13 for (int r = 0; r < numRows; ++r) {
14 for (int j = r; j < n; j += cycleLen) {
15 res += s[j];
16 // Middle rows have diagonal characters
17 if (r > 0 && r < numRows - 1) {
18 int diag = j + cycleLen - 2 * r;
19 if (diag < n) {
20 res += s[diag];
21 }
22 }
23 }
24 }
25 return res;
26 }
27};
28
29int main() {
30 Solution sol;
31 std::cout << sol.convert("PAYPALISHIRING", 3) << std::endl; // PAHNAPLSIIGYIR
32 std::cout << sol.convert("PAYPALISHIRING", 4) << std::endl; // PINALSIGYAHRPI
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) strictly — Every character in s is visited exactly once in output order.
  • Space complexity: O(1) extra space (excluding output string)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.2D Matrix Grid SimulationO(numRows * N)O(numRows * N)Visually represents the exact visual grid.Wastes space on empty matrix cells.
2.Row String Buffers SimulationO(N)O(N)Extremely intuitive: bounce currRow and step = +1 / -1.Allocates numRows separate string builder objects.
3.Pure Mathematical Index Jumping (Optimal)OptimalO(N)O(1) extra spaceDirectly calculates output string characters in exact order; zero intermediate buffer arrays.Requires indexing arithmetic for diagonal elements.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Dividing or modulo by 2 * numRows - 2 when numRows == 1 resulting in division by zero.

Pitfall 2:

Forgetting the boundary check diag < n when extracting diagonal elements in the last cycle.

Crucial Edge Cases to Validate:

  • numRows == 1: Early return returns s unchanged immediately.
  • numRows >= s.length: Early return returns s unchanged.
  • Short string (s = AB, numRows = 1): Returns AB.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the cycle length formula 2 * numRows - 2 and explain the top row, bottom row, and diagonal row math.
  2. Remember the guard condition numRows == 1 || numRows >= s.length.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the cycle length formula for a zigzag pattern with numRows rows?

Back to DSA Sheet