MediumStringUpdated Sep 2026

6. Zigzag Conversion

Asked at Oracle, Walmart, Bloomberg

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

String

Companies

3

Problem

You are given a string s and a number numRows. Imagine writing the characters of s in a zigzag shape across numRows rows: you go straight down filling one character per row, and when you reach the bottom row you go diagonally up-right until you reach the top row, then down again, and so on. The first character always starts at the top row.

After all characters are placed, read the rows from top to bottom, and inside each row from left to right. Return the resulting string.

If numRows is 1, or if numRows is at least the length of s, no real zigzag happens — every character stays on its own line in order, so the answer is just s unchanged.

Where each character lands

read rowsrow 0row 1row 2PAHNAPLSIIGYIRConcatenating the three rows top to bottom produces the answer.
Writing PAYPALISHIRING on 3 rows in a zigzag, then reading row by row, gives PAHNAPLSIIGYIR.

Constraints

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

Examples

Example 1
Inputs = "PAYPALISHIRING", numRows = 3
Output"PAHNAPLSIIGYIR"
WhyThe characters land on rows 0,1,2,1,0,1,2,1,0,... so row 0 gets P,A,H,N; row 1 gets A,P,L,S,I,I,G; row 2 gets Y,I,R. Reading the rows top to bottom gives PAHN + APLSIIG + YIR.
Example 2
Inputs = "PAYPALISHIRING", numRows = 4
Output"PINALSIGYAHRPI"
WhyWith 4 rows the down-up cycle is longer, so the rows collect P,I,N / A,L,S,I,G / Y,A,H,R / P,I. Joining them top to bottom gives PINALSIGYAHRPI.
Example 3
Inputs = "A", numRows = 1
Output"A"
WhyThere is only one character and only one row, so nothing moves and the string stays the same.

Asked At

3 companies
CompanyDifficulty
OracleMediumView all Oracle questions →
WalmartMediumView all Walmart questions →
BloombergMediumView all Bloomberg 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

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.

3

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.

4

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, ...

5

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.

Simulate the bouncing row pointer

rows = ["", "", ""]row = 0, dir = +1append char to rows[row]flip dir at row 0 or row 2row += dirEach character goes into the bucket of the currentrow, then the pointer steps up or down.buckets after 5 chars01012PAAPYAfter P,A,Y,P,A the pointer is back on row 0, so thenext character A goes there.final buckets0123456012PAHNAPLSIIGYIRAt the end, join the buckets in order: PAHN + APLSIIG+ YIR.cycle length = 2 * numRows - 2row 0 and row numRows-1 flip directionanswer = ''.join(rows)
Keep one bucket per row and a direction flag that flips at the top and bottom rows.
ComplexityTime O(n)Space O(n)Each character is appended to exactly one row once, and the final join copies all n characters, so the work grows linearly with the input size.

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

O(n) time
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 runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Zigzag Conversion?

Zigzag Conversion is asked at Oracle, Walmart, Bloomberg. 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.