6. Zigzag Conversion

MediumMatrix and SimulationBucketing into rowsRow-index simulation with bouncing direction

Zigzag Conversion

Given a string s and an integer numRows, write s in a zigzag pattern down and up across numRows rows, then read the pattern row by row to produce a new string. Return that concatenated string.

Open official problem prompt ↗

In plain English

Re-order the characters of a string so that they read out in the order a zigzag path would visit them across numRows rows.

Picture it like this

Imagine writing a message on a set of horizontal lines while your pen bounces down to the bottom line and back up to the top, like a ping-pong ball; afterward you read each line left to right.

Example

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Why: Row 0 is P A H N, row 1 is A P L S I I G, row 2 is Y I R; concatenated they give PAHNAPLSIIGYIR.

Constraints

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

Pattern lesson

See the pattern, then code

Row-index simulation with bouncing direction

↗

Matrix and Simulation

Rotations, boundary walks, direction changes, or careful in-place state updates.. Assign each character to a row. The row index marches down until it hits the last row, then reverses and marches up until it hits row 0, and so on. Appending characters to per-row buckets in this order reproduces the zigzag exactly.

New words, made simpleKnow these before the algorithm

Zigzag: A path that goes straight down the rows, then diagonally back up, repeating.
Row bucket: A string that collects every character that lands on a given row.
Bounce: Reversing the vertical direction when the top or bottom row is reached.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Coordinate math per cell

Works but the index arithmetic is easy to get wrong and harder to read.

Compute for each character which row it belongs to using the cycle length 2*numRows-2 and place it.

Time O(n)Space O(n)

Best choiceBouncing row simulation

Simple, single pass, no error-prone modular math.

Walk the string once, appending each character to the current row and flipping direction at the edges.

Time O(n)Space O(n)

The rule we keep true

Invariant

At every step, cur is the row the next character belongs to, and step points toward the edge we have not most recently touched.

Why this is correct

Reasoning

The zigzag visits rows in the exact sequence 0,1,...,numRows-1,numRows-2,...,1,0,1,... The bouncing counter reproduces that sequence, so appending in visit order and then reading row by row is equivalent to physically drawing the zigzag and reading it.

The algorithm in three movesSay these aloud before coding

1Handle numRows == 1 as a no-op returning s

cur=0 P -> down

2Keep a list of row buckets and a current row plus a step of +1/-1

cur=1 A -> down

3For each character, append it to the current row, flip the step at the top or bottom row, then move the row index by step

cur=2 Y -> bounce up

4Join all row buckets in order

cur=1 P -> up

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · ReadP

2 · AskWhich row?

3 · Update statecur=0, step=1

4 · Resultrows[0]='P', move to cur=1

Key takeaway

The first characters of PAYPAL descending then ascending across 3 rows as the direction bounces.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Single-row shortcut
With one row the zigzag is just the original string, and it also avoids a divide-by-zero-style edge in the bounce logic.
2
Lines 5-6Set up buckets and walker
rows holds one string per row; cur and step track position and direction.
3
Lines 7-13Bounce loop
Append the character, then reset step to +1 at the top or -1 at the bottom, then advance cur.
4
Lines 14Concatenate
Reading rows top to bottom yields the zigzag string.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

numRows == 1 (output equals input)
numRows >= len(s) so no row ever fills past one column
Very short strings of length 1

Common beginner mistakes

Forgetting the numRows == 1 guard, which never flips step and would leave cur stuck or index out of range logic
Flipping direction based on a wrong comparison (using > instead of == at the edges)
Trying to build the output column by column instead of row by row

Check your understanding

Why is the numRows == 1 case handled separately?

Zigzag Conversion

Zigzag Conversion

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Matrix and Simulation