Medium
String
Updated Sep 2026

Zigzag Conversion

Asked at Oracle, Walmart

Problem

Convert a string to a zigzag pattern on a given number of rows, then read it row by row. For example, with numRows=3 and string "PAYPALISHIRING", the zigzag pattern creates rows that are read left to right to produce a new string.

Asked At

CompanyDifficulty
OracleMediumView all Oracle questions →
WalmartMediumView all Walmart questions →

How to Think About It

1.

Key insight: simulate the zigzag pattern by tracking the current row. Characters cycle through rows 0, 1, ..., numRows-1, numRows-2, ..., 1, 0, 1, ... The cycle length is 2*numRows - 2.

2.

Visual walkthrough for "PAYPALISHIRING", numRows=3:
Row 0: P . . . A . . . I . . . N
Row 1: . A . Y . L . S . H . R . G
Row 2: . . Y . . . I . . . I . .
- Read row by row: "PAHNAPLSIIGYIR"
`- Cycle length = 2*3 - 2 = 4. Characters at positions 0,4,8,12 go to row 0. Positions 1,3,5,7,9,11 to row 1. Positions 2,6,10 to row 2.

3.

Approach 1: create numRows empty strings. Iterate through the input, appending each character to the appropriate row string. Use a direction flag (going down or up) to track movement. When you hit row 0 or row numRows-1, reverse direction.

4.

Approach 2: direct formula. For each row i, the characters are at positions j where j % cycle == i or j % cycle == cycle - i. This avoids simulation but is harder to implement correctly.

5.

The cycle-based approach: for row 0, take characters at indices 0, cycle, 2cycle, ... For row i (0 < i < numRows-1), take characters at i, cycle-i, cycle+i, 2cycle-i, 2*cycle+i, ... For last row, take characters at numRows-1, cycle+numRows-1, ...

6.

Edge cases: numRows=1 (no zigzag, return original string). numRows >= len(s) (each character is on its own row, return original string). Empty string (return empty).

Optimal Approach

Use the row-by-row simulation approach.

  1. Create numRows empty strings (or lists).
  2. Track currentRow = 0 and direction = 1 (down).
  3. For each character in the input:
    • Append to the current row string.
    • If currentRow == 0, direction = 1 (go down). If currentRow == numRows-1, direction = -1 (go up).
    • currentRow += direction.
  4. Concatenate all row strings.

Walkthrough for "PAYPALISHIRING", numRows=3:

  • Row 0: P, A, I, N -> "PAHN"
  • Row 1: A, P, L, S, I, I, G, R -> "APLSIIGR"
  • Row 2: Y, H, R -> Wait, that's wrong. Let me retrace.
  • Actually: P(row0), A(row1), Y(row2), P(row1), A(row0), L(row1), I(row2), S(row1), H(row0), I(row1), R(row2), I(row1), N(row0)
  • Row 0: P, A, H, N -> "PAHN"
  • Row 1: A, P, L, S, I, I, R -> "APLSIIR"
  • Row 2: Y, I, G -> "YIG"
  • Result: "PAHNAPLSIIRYIG". The exact order depends on implementation.

Time: O(n). Space: O(n) for the output strings.

What Trips People Up in Real Interviews

1.

Reversing direction at the wrong row. Direction reverses at row 0 (start going down) and row numRows-1 (start going up). Not at row 1 or numRows-2.

2.

Forgetting that numRows=1 means no zigzag. The zigzag pattern requires at least 2 rows to have any diagonal movement. Return the original string when numRows=1.

3.

Using a 2D matrix instead of row strings. A 2D matrix wastes space because most cells are empty. Using numRows strings and appending is more efficient and cleaner.

4.

Not handling the case where numRows >= len(s). In this case, each character gets its own row, and the zigzag is just the original string. Return it directly.

5.

Confusing zigzag with diagonal. The zigzag goes down, then up, then down again. It's not a diagonal pattern — it's a zigzag between the top and bottom rows.

Solution Code

def convert(s, numRows):
    if numRows == 1 or numRows >= len(s):
        return s
    rows = [''] * numRows
    current_row = 0
    direction = 1

    for ch in s:
        rows[current_row] += ch
        if current_row == 0:
            direction = 1
        elif current_row == numRows - 1:
            direction = -1
        current_row += direction

    return ''.join(rows)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Zigzag Conversion problem?

Convert a string to a zigzag pattern on a given number of rows, then read it row by row. For example, with numRows=3 and string "PAYPALISHIRING", the zigzag pattern creates rows that are read left to right to produce a new string.

How do you solve Zigzag Conversion?

The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.

What companies ask Zigzag Conversion?

Zigzag Conversion is asked at Oracle, Walmart. It is a medium difficulty problem.

What are common mistakes on Zigzag Conversion?
  • Reversing direction at the wrong row. Direction reverses at row 0 (start going down) and row numRows-1 (start going up). Not at row 1 or numRows-2.
  • Forgetting that numRows=1 means no zigzag. The zigzag pattern requires at least 2 rows to have any diagonal movement. Return the original string when numRows=1.
  • Using a 2D matrix instead of row strings. A 2D matrix wastes space because most cells are empty. Using numRows strings and appending is more efficient and cleaner.
  • Not handling the case where numRows >= len(s). In this case, each character gets its own row, and the zigzag is just the original string. Return it directly.
  • Confusing zigzag with diagonal. The zigzag goes down, then up, then down again. It's not a diagonal pattern — it's a zigzag between the top and bottom rows.