Problem Statement

Zigzag Conversion

Picture writing a word on paper, but instead of going straight across, your pen moves in a zigzag. It goes down a few rows, then back up at an angle, then down again, over and over. After the whole word is written that way, you read it back one row at a time, left to right. That gives you a new, scrambled string. For example, "PAYPALISHIRING" with 3 rows lays out as P-A-H-N on the top row, A-P-L-S-I-I-G on the middle row, and Y-I-R on the bottom row. Reading those rows in order gives "PAHNAPLSIIGYIR". The trick we use is to copy the zigzag as we go. We keep one bucket for each row, and we keep a direction flag that tells us whether the pen is currently moving down or up. We walk through the string one letter at a time, drop each letter into the row our pen is on, and flip the direction whenever we touch the top row or the bottom row.

mediumStringStringsTime: O(n) · Space: O(n)

Signals to notice

write string in zigzag across rowsread row by rowoscillating row index

Brute force first

Build a 2D grid — O(n × numRows) space.

The key insight

Array of strings (one per row). Walk through string assigning each char to its row. Row bounces: 0→numRows-1→0→... O(n).

Trace it on `s="PAYPALISHIRING", numRows=3`

init: rows=['','',''], row=0, down=false
'P'→rows=['P','',''], top so down=true, row→1
'A'→rows=['P','A',''], row→2; 'Y'→rows=['P','A','Y'], bottom so down=false, row→1
'P'→rows=['P','AP','Y'], row→0; 'A'→rows=['PA','AP','Y'], top so down=true, row→1
'L','I','S'→rows=['PA','APLS','YI'], 'I' bounced bottom (down=false), 'S' lands row1 going up, row→0
'H','I','R'→rows=['PAH','APLSI','YIR'], 'H' top so down=true, 'R' bottom so down=false, row→1
'I','N','G'→rows=['PAHN','APLSIIG','YIR'], 'N' top so down=true
concat rows → "PAHNAPLSIIGYIR"

What must stay true

The row index oscillates between 0 and numRows-1. Each character appends to its row's string. Concatenating all rows gives the result.

Shape of the loop

if numRows == 1 or numRows >= len(s): return s
rows = ['' for each of numRows]; row = 0; down = false
for ch in s:
    rows[row] += ch
    if row == 0 or row == numRows - 1: down = not down
    row += down ? +1 : -1
return concat(rows)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Edge case: numRows = 1 → return the original string. No zigzag needed.

Strings Pattern