How do you solve Zigzag Conversion?

Initialize an array of empty strings for each row. Iterate over each character in s, appending it to the current row's string. Update the current row by moving in the current direction. Reverse direction when the top or bottom row is reached. Finally, concatenate all row strings to form the output.

Zigzag Conversion

Q: What is the time complexity of Zigzag Conversion?

O(n). Each character in the input string is processed exactly once, appending to one of the row strings, resulting in linear time complexity.

Q: What pattern does Zigzag Conversion use?

The Pattern: Simulation (Stateful Traversal) The Heuristic: When a problem requires constructing or interpreting a pattern with directional changes or cycles, simulate the process by tracking state variables (like current position and direction) instead of building explicit data structures, enabling efficient and clear solutions.

Medium Simulation

Problem

Given a string s and an integer numRows, return the string formed by writing s in a zigzag pattern on numRows and then reading line by line.

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

Example

Input: s = "PAYPALISHIRING", numRows = 3

Output: "PAHNAPLSIIGYIR"

The zigzag pattern for numRows=3 is: P A H N A P L S I I G Y I R Reading line by line produces "PAHNAPLSIIGYIR". The algorithm simulates placing characters row by row, changing direction when reaching the top or bottom row. The critical moment is when the direction reverses at the boundaries, ensuring characters are assigned to the correct rows in zigzag order.

Approach

Straightforward Solution

A brute-force approach might try to build a 2D matrix representing the zigzag and then read it line by line. This wastes space and complicates indexing, especially for large strings and row counts.

Core Observation

The zigzag pattern can be viewed as placing characters sequentially in rows, moving downwards until the bottom row, then upwards until the top row, repeatedly. This movement creates a repeating cycle of row indices.

Path to Optimal

Preview

The key insight is to simulate the zigzag traversal by tracking the current row and direction (down or up). Instead of building a matrix, maintain an array of strings for each row and append characters accordingly…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize an array of empty strings for each row. Iterate over each character in s, appending it to the current row's string…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each character in the input string is processed exactly once, appending to one of the row strings, resulting in linear time complexity.

Space

O(n)

The auxiliary space is proportional to the input size, as all characters are stored distributed across the row strings before concatenation. This is necessary since the output string length equals the input length.

Pattern Spotlight

Simulation (Stateful Traversal)

When a problem requires constructing or interpreting a pattern with directional changes or cycles, simulate the process by tracking state variables (like current position and direction) instead of building explicit data structures, enabling efficient and clear solutions.

Solution

Python

1class Solution:
  def convert(self, s: str, numRows: int) -> str:
      if numRows == 1:
          return s
5
      rows = [""] * numRows
      row = 0
      direction = 1
9
      for ch in s:
          rows[row] += ch
12
          if row == 0:
              direction = 1
          elif row == numRows - 1:
              direction = -1
17
          row += direction
19
      return "".join(rows)

Step-by-Step Solution

Handle Single Row Edge Case to Avoid Unnecessary Processing

3if numRows == 1:
4    return s

Objective

To immediately return the input string if numRows is 1, since the zigzag pattern degenerates to a straight line.

Key Insight

When numRows is 1, the zigzag pattern is just the original string itself. This early exit prevents unnecessary computation and avoids edge case bugs related to direction changes and row indexing.

Interview Quick-Check

Core Logic

Recognizing that numRows=1 means no zigzag occurs and the input string is the output.

Common Pitfalls & Bugs

Failing to handle numRows=1 separately can cause index errors or incorrect direction changes.

Initialize Row Containers and Directional State for Zigzag Simulation

To prepare an array of strings for each row and initialize variables to track the current row and traversal direction.

Simulate Zigzag Traversal by Appending Characters and Updating Direction

To iterate over each character in the input string, append it to the current row, and update the current row index and direction accordingly.

Concatenate Row Strings to Form Final Zigzag Converted Output

To combine all row strings into a single output string representing the zigzag conversion.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 3 Critical

if numRows == 1:

Check if numRows is 1 to handle the trivial zigzag case.

When numRows is 1, the zigzag pattern is just the original string, so returning early avoids unnecessary computation and prevents errors related to direction changes.

Line 11 Critical

rows[row] += ch

Append the current character to the string of the current row.

Assigning characters to rows as they appear simulates the zigzag pattern without building a full matrix.

Line 18 Critical

row += direction

Update the current row index by adding the direction.

Incrementing or decrementing the row index simulates moving down or up the zigzag pattern, ensuring characters are assigned to the correct rows.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why is it necessary to reverse the direction when the current row reaches the top or bottom?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Zigzag Conversion from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Zigzag Conversion drill

or drill a free problem

1	`class Solution:`
2	`def convert(self, s: str, numRows: int) -> str:`
3	`if numRows == 1:`
4	`return s`
5
6	`rows = [""] * numRows`
7	`row = 0`
8	`direction = 1`
9
10	`for ch in s:`
11	`rows[row] += ch`
12
13	`if row == 0:`
14	`direction = 1`
15	`elif row == numRows - 1:`
16	`direction = -1`
17
18	`row += direction`
19
20	`return "".join(rows)`