Loading…

mediumStringsLC #6Sometimes asked

Zigzag Conversion

Q: How do you solve Zigzag Conversion using the Direct Index by Cycle Formula (O(1) Extra Space) approach?

When to use it: Offer when asked to avoid the row buffers or when numRows is huge. Frame it around the period 2·numRows − 2. Instead of simulating the walk, we compute *directly* which characters belong to each row by exploiting the period of the zigzag. One complete cycle — down `numRows` steps then back up to just below the top — spans `cycle = 2·numRows − 2` characters. **The edge rows are simple.** Row 0 contains the characters at indices `0, cycle, 2·cycle, …` — one per cycle, because the pen touches the top exactly once each cycle. The last row (`numRows − 1`) is the same: one character per cycle, starting at index `numRows − 1`. So for these two rows we just step by `cycle`. **The middle rows have a second character per cycle — the diagonal one.** While ascending, the pen passes through each middle row a second time. For row `r`, that diagonal character sits at index `i + cycle − 2·r`, where `i` is the 'descending' index for that cycle. Intuitively, `2·r` measures how far down the row is, and `cycle − 2·r` is the offset from the descending hit to the ascending hit within the same cycle. We emit that extra character only when its index is still within the string (`diag < n`), which guards the final partial cycle. **Why this is worth knowing.** The simulation allocates `numRows` buffers; if `numRows` is large (up to 1000 here) but the string is short, most buffers sit empty — wasteful. The formula approach writes straight into the output in final order, using only the loop variables. The cost is the index arithmetic, which is easy to get subtly wrong, so I'd present the simulation first for clarity and reach for this when O(1) extra space or large `numRows` is the explicit concern. **Both are O(n) time; they differ in memory and in how much arithmetic you have to defend.** Time complexity: O(n). Space complexity: O(1).

LCPractice

Arrays & Hashing · 26 of 83 · 9 min

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this (you may want to display this pattern in a fixed font for better legibility):

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR".

Write the code that will take a string and make this conversion given a number of rows.

In plain English

Characters are written diagonally in a down-then-up zigzag across numRows rows, but the answer is read straight across each row, top to bottom. We need to figure out, for each character, which row it lands in — either by simulating the walk or by computing the row's indices directly.

Examples

Example 1

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Note: Row 0: PAHN, Row 1: APLSIIG, Row 2: YIR. Concatenated row by row.

Example 2

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Note: Row 0: PIN, Row 1: ALSIG, Row 2: YAHR, Row 3: PI. The diagonals are longer with more rows.

Example 3

Input: s = "A", numRows = 1
Output: "A"
Note: Single row → output equals input. The numRows == 1 guard returns immediately.

Constraints

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

Clarifying questions4First question: What happens when numRows is 1?Explore questions

Q1.What happens when numRows is 1?
The zigzag collapses to a single horizontal line, so the output equals the input. This must be special-cased — it's the classic trap.
Q2.Can numRows exceed the string length?
Yes. Then the string never reaches the bottom; it just goes straight down partway. The simulation handles this naturally; the math version must guard indices.
Q3.Is the output read row by row, left to right?
Yes — top row first, then the next, concatenated. The writing is diagonal but the reading is horizontal.
Q4.Do non-letter characters (',', '.') affect the pattern?
No — every character, whatever it is, occupies one cell in the zigzag. They're treated identically.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Simulate writing the string into `numRows` buckets. Walk the characters once, appending each to the current row, and bounce the row index between 0 and numRows−1 with a direction that flips at the top and bottom. Concatenate the rows. O(n) time, O(n) space — and crucially, handle numRows == 1 by returning s unchanged.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can translate a visual/geometric pattern into index arithmetic, and whether you remember the numRows == 1 edge case that breaks naive bouncing logic.

Where candidates slip

Forgetting the numRows == 1 guard (direction never flips), or mismanaging the direction so the pointer walks off the row range, or reading the rows in the wrong order.

How to stand out

Start with the clean bouncing-direction simulation, then mention you can avoid the row buffers entirely with the cycle = 2·numRows−2 formula and direct index math — showing you understand the underlying periodicity.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Row Simulation with Bouncing Direction (Optimal, Intuitive)Optimal	`O(n)`	`O(n)`	Lead with this. It's the clearest mental model — literally write the characters into rows the way the diagram shows.	Read
2	Direct Index by Cycle Formula (O(1) Extra Space)	`O(n)`	`O(1)`	Offer when asked to avoid the row buffers or when numRows is huge. Frame it around the period 2·numRows − 2.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFor each char ccur == 0?YesNoExplore the full tree

The bouncing row index

How to read it:The current row walks down to numRows−1, flips direction, walks back up to 0, and repeats.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Row Simulation with Bouncing Direction (Optimal, Intuitive)

TimeO(n)SpaceO(n)

Lead with this. It's the clearest mental model — literally write the characters into rows the way the diagram shows.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Imagine actually writing the characters into the grid. You move down one row at a time, and when you hit the bottom you start moving up. What variable tracks which row you're on?

2Hint 2Explore hint

Keep one string buffer per row. Append each character to the current row, then update the row index by a step that is +1 going down and −1 going up.

3Hint 3Explore hint

Flip the step to +1 when you reach row 0 and to −1 when you reach row numRows−1. At the end, concatenate the row buffers top to bottom. Don't forget: if numRows == 1, just return s.

A · Core idea

This approach mirrors exactly what the diagram shows: you write the string into a set of rows, moving diagonally, then read the rows back in order. We keep one buffer per row and a cur index for which row the 'pen' is currently on.

The direction bounce is the heart of it. As we place characters, cur increases (moving down the page) until it reaches the bottom row numRows − 1, at which point the zigzag turns and cur must start decreasing (moving up the diagonal). We capture this with a step variable that is +1 while descending and −1 while ascending. The crucial detail is when to flip: we set step = +1 the moment cur is 0, and step = -1 the moment cur is numRows − 1. Checking the boundary before moving guarantees cur never leaves the valid [0, numRows−1] range, so we never index out of bounds and never skip the edge rows.

Why `numRows == 1` must be special-cased. If there is only one row, cur is always 0, which is also the last row index numRows − 1 = 0. Our flip logic would set step = +1 (because cur == 0) and the code would then try to move to row 1, which doesn't exist — or, depending on ordering, the direction logic becomes contradictory. The single-row zigzag is just the original string, so we short-circuit and return s immediately. This guard is the most-failed part of the problem in interviews.

Why reading is row-by-row. The subtlety that makes this a real problem rather than a no-op is that the characters are written on diagonals but read horizontally. After the walk, row 0 holds every character that landed on the top line, row 1 the next, and so on. Concatenating the buffers from the top row down reassembles the string in the required zigzag-read order. The whole trick is keeping the write order (diagonal) and read order (horizontal) cleanly separated by bucketing into rows.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "PAYPALISHIRING", numRows = 3

Interactive diagram

Write diagonal, read horizontal

P (cur=0)

Active call / nodeSupporting contextReturned stateNot active

Characters are bucketed by row during the walk, then the rows are concatenated.

Final result"PAHNAPLSIIGYIR"

C · Code with teaching comments

solution.javaJava

Row Simulation with Bouncing Direction (Optimal, Intuitive) — optimal

4 teaching notes

1
public String convert(String s, int numRows) {
2
    // Guard the degenerate case — one row means the output is the input; bouncing logic
3
    // would otherwise misbehave.
4
    if (numRows == 1) {
5
        return s;
6
    }
7
    StringBuilder[] rows = new StringBuilder[numRows];
8
    for (int i = 0; i < numRows; i++) {
9
        rows[i] = new StringBuilder();
10
    }
11
    int cur = 0, step = 1;
12
    for (char c : s.toCharArray()) {
13
        // Drop the current character into whichever row the pen is on.
14
        rows[cur].append(c);
15
        if (cur == 0) {
16
            step = 1;
17
        } else if (cur == numRows - 1) {
18
            step = -1;
19
        }
20
        cur += step;
21
    }
22
    StringBuilder result = new StringBuilder();
23
    for (StringBuilder row : rows) {
24
        result.append(row);
25
    }
26
    return result.toString();
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Modeling 'write diagonally, read horizontally' as buckets-by-row turns a confusing geometric description into a five-line loop. The bouncing step that flips only at the two edge rows is a tidy way to traverse any back-and-forth pattern without overshooting.

ComplexityO(n) time, O(n) space — Each of the n characters is appended exactly once and the final concatenation touches each character once more → O(n) time. We store all n characters across the row buffers → O(n) extra space.

E · Edge cases and pitfalls7numRows = 1 — Returns s unchanged via the guard.Explore edge cases

Edge cases handled

numRows = 1Returns s unchanged via the guard.
numRows >= s.length()Pen never reaches the bottom; each early row gets one char, later rows stay empty. Concatenation still yields s reordered correctly.
s of length 2, numRows = 5Only rows 0 and 1 get a character; remaining rows are empty buffers and contribute nothing.

Pitfalls

Omitting the numRows == 1 guard — direction logic breaks or indexes row 1 that doesn't exist.
Flipping direction after moving instead of at the boundary — pointer walks out of range.
Reading rows in the wrong order or forgetting to concatenate all of them.
Using string += in a tight loop in Java instead of StringBuilder — quadratic time.

03.2

Approach 2 of 2

Direct Index by Cycle Formula (O(1) Extra Space)

TimeO(n)SpaceO(1)

Offer when asked to avoid the row buffers or when numRows is huge. Frame it around the period 2·numRows − 2.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the top row's indices in PAYPALISHIRING with 3 rows: 0, 4, 8, 12 — they differ by a fixed cycle. What is that cycle in terms of numRows?

2Hint 2Explore hint

One full down-and-up cycle covers 2·numRows − 2 characters. The first and last rows have exactly one character per cycle.

3Hint 3Explore hint

Middle rows have a second 'diagonal' character per cycle, located at index i + cycle − 2·row. Emit it when it's within bounds, and you never need row buffers.

A · Core idea

Instead of simulating the walk, we compute directly which characters belong to each row by exploiting the period of the zigzag. One complete cycle — down numRows steps then back up to just below the top — spans cycle = 2·numRows − 2 characters.

The edge rows are simple. Row 0 contains the characters at indices 0, cycle, 2·cycle, … — one per cycle, because the pen touches the top exactly once each cycle. The last row (numRows − 1) is the same: one character per cycle, starting at index numRows − 1. So for these two rows we just step by cycle.

The middle rows have a second character per cycle — the diagonal one. While ascending, the pen passes through each middle row a second time. For row r, that diagonal character sits at index i + cycle − 2·r, where i is the 'descending' index for that cycle. Intuitively, 2·r measures how far down the row is, and cycle − 2·r is the offset from the descending hit to the ascending hit within the same cycle. We emit that extra character only when its index is still within the string (diag < n), which guards the final partial cycle.

Why this is worth knowing. The simulation allocates numRows buffers; if numRows is large (up to 1000 here) but the string is short, most buffers sit empty — wasteful. The formula approach writes straight into the output in final order, using only the loop variables. The cost is the index arithmetic, which is easy to get subtly wrong, so I'd present the simulation first for clarity and reach for this when O(1) extra space or large numRows is the explicit concern. Both are O(n) time; they differ in memory and in how much arithmetic you have to defend.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "PAYPALISHIRING", numRows = 3

row 0

i = 0,4,8,12 → P,A,H,N

Stateresult = "PAHN"

Final result"PAHNAPLSIIGYIR"

C · Code with teaching comments

Reference implementation previewpublic String convert(String s, int numRows) { if (numRows == 1) { return s; } int n = s.length();Explore the full code

solution.javaJava

Direct Index by Cycle Formula (O(1) Extra Space) — reference

4 teaching notes

1
public String convert(String s, int numRows) {
2
    if (numRows == 1) {
3
        return s;
4
    }
5
    int n = s.length();
6
    // Characters per full down-and-up zigzag cycle — the period of the pattern.
7
    int cycle = 2 * numRows - 2;
8
    StringBuilder sb = new StringBuilder();
9
    for (int r = 0; r < numRows; r++) {
10
        // Each row's primary characters start at index r and recur every cycle.
11
        for (int i = r; i < n; i += cycle) {
12
            sb.append(s.charAt(i));
13
            // Only middle rows have the extra diagonal character per cycle.
14
            if (r != 0 && r != numRows - 1) {
15
                // Index of the ascending (diagonal) hit within the same cycle; emit
16
                // only if diag < n.
17
                int diag = i + cycle - 2 * r;
18
                if (diag < n) {
19
                    sb.append(s.charAt(diag));
20
                }
21
            }
22
        }
23
    }
24
    return sb.toString();
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Recognising the period 2·numRows − 2 converts the geometric pattern into closed-form index math. The middle-row diagonal at i + cycle − 2·r is the one non-obvious term — derive it once from a small example and it generalises.

ComplexityO(n) time, O(1) space — We visit each character index at most once across all rows (the diagonal element of a middle row is the only extra emit, and it's still distinct), so total emits = n → O(n) time. We append directly to the result without per-row buffers → O(1) extra space beyond the output.

E · Edge cases and pitfalls7numRows = 1 — Guarded early return; cycle would be 0 and cause an infinite loop otherwise.Explore edge cases

Edge cases handled

numRows = 1Guarded early return; cycle would be 0 and cause an infinite loop otherwise.
numRows = 2cycle = 2; no middle rows, so it's two simple strided scans (even indices, then odd).
last partial cyclediag >= n on the final cycle of a middle row → the guard skips it, preventing an out-of-bounds.

Pitfalls

Forgetting the numRows == 1 guard — cycle becomes 0 and the loop never advances (infinite loop).
Emitting the diagonal char for edge rows — duplicates characters.
Omitting the diag < n bounds check — out-of-bounds on the final partial cycle.
Deriving the diagonal offset wrong — verify with a tiny example before trusting it.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String convert(String s, int numRows) { if (numRows == 1) { return s; } StringBuilder[] rows = new StringBuilder[numRows];Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the numRows == 1 guard

With one row, cur is always both 0 and the last index, so the bounce logic is contradictory; in the formula version cycle = 0 causes an infinite loop.

Explore the code comparison

Don't write this

rows = [''] * numRows
cur, step = 0, 1
for c in s:
    rows[cur] += c
    ...  # numRows == 1 never handled

Write this instead

if numRows == 1:
    return s
rows = [''] * numRows
cur, step = 0, 1
...

Flipping direction after overshooting

If you move first and then check, cur can become numRows (out of range) before you correct it.

Explore the code comparison

Don't write this

rows[cur].append(c);
cur += step;
if (cur == numRows) { step = -1; cur -= 2; }  // brittle correction

Write this instead

rows[cur].append(c);
if (cur == 0) step = 1;
else if (cur == numRows - 1) step = -1;
cur += step;

Emitting the diagonal for edge rows (formula version)

Rows 0 and numRows−1 have no second diagonal character; emitting one duplicates characters and corrupts the output.

Explore the code comparison

Don't write this

result.append(s[i])
diag = i + cycle - 2 * r
if diag < n:
    result.append(s[diag])  # wrong for r == 0 or r == numRows-1

Write this instead

result.append(s[i])
if r != 0 and r != numRows - 1:
    diag = i + cycle - 2 * r
    if diag < n:
        result.append(s[diag])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Row-bucket simulation with bouncing direction

Code pattern to memorize

if numRows == 1: return s
rows = [''] * numRows; cur = 0; step = 1
for c in s:
    rows[cur] += c
    if cur == 0: step = 1
    elif cur == numRows-1: step = -1
    cur += step
return ''.join(rows)

Rules to remember

1Guard `numRows == 1` first. With one row the zigzag is the original string; without the guard the direction never flips and step logic divides by a degenerate range.
2Flip direction AT the boundaries, not after overshooting. Set step = +1 when at row 0 and step = -1 when at the last row.
3Reading order is row-by-row, top to bottom — concatenate the buckets in order at the end.
4The cycle length is `2·numRows − 2` — the number of characters between two appearances in the same edge row. Useful for the O(1)-space math variant.
5The answer is read horizontally even though the string is written diagonally — that mismatch is the whole problem.

Use this pattern when

You must reorder characters according to a fixed geometric/positional pattern
The pattern repeats with a clear period (here, a zigzag cycle)
Direct simulation of 'place each item where it goes' is clear and linear
You can either bucket by destination or compute each destination index by formula

Choose another pattern when

The transformation is a simple reverse or rotation → no row buckets needed
There's no periodic geometry, just per-character mapping → plain map/transform
You need the inverse (zigzag string back to original) → different index math
numRows is huge relative to n → most rows are empty; the math variant avoids allocating them

Interview takeaway

Zigzag is a 'place each character where the pattern says, then read it back differently' problem. The bouncing-index simulation is the intuitive O(n) answer; the cycle-formula version computes each row's indices directly and saves the row buffers. Recognising the period 2·numRows−2 is the key insight either way.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPositional simulation: place each character where a periodic geometric pattern dictates, then read it back in a different order. The bouncing-index walk is the intuitive form; the cycle = 2·numRows−2 formula computes destinations directly. Same 'simulate the layout' family as Text Justification and Count and Say.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count and Say
Coming soon
Another build-a-string-by-simulation problem — generate each term from the previous.
Encode and Decode Strings
String construction with a positional scheme you must invert exactly.
Text Justification
Heavier simulation: lay characters out under positional rules, then read them back formatted.

Same pattern

←

Word Pattern

Continue · Next problem

Divisible Sum Pairs

mediumStringsLC #6Sometimes asked

Zigzag Conversion

LCPractice

Arrays & Hashing · 26 of 83 · 9 min

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this (you may want to display this pattern in a fixed font for better legibility):

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR".

Write the code that will take a string and make this conversion given a number of rows.

In plain English

Examples

Example 1

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Note: Row 0: PAHN, Row 1: APLSIIG, Row 2: YIR. Concatenated row by row.

Example 2

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Note: Row 0: PIN, Row 1: ALSIG, Row 2: YAHR, Row 3: PI. The diagonals are longer with more rows.

Example 3

Input: s = "A", numRows = 1
Output: "A"
Note: Single row → output equals input. The numRows == 1 guard returns immediately.

Constraints

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

Clarifying questions4First question: What happens when numRows is 1?Explore questions

Q1.What happens when numRows is 1?
The zigzag collapses to a single horizontal line, so the output equals the input. This must be special-cased — it's the classic trap.
Q2.Can numRows exceed the string length?
Yes. Then the string never reaches the bottom; it just goes straight down partway. The simulation handles this naturally; the math version must guard indices.
Q3.Is the output read row by row, left to right?
Yes — top row first, then the next, concatenated. The writing is diagonal but the reading is horizontal.
Q4.Do non-letter characters (',', '.') affect the pattern?
No — every character, whatever it is, occupies one cell in the zigzag. They're treated identically.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can translate a visual/geometric pattern into index arithmetic, and whether you remember the numRows == 1 edge case that breaks naive bouncing logic.

Where candidates slip

Forgetting the numRows == 1 guard (direction never flips), or mismanaging the direction so the pointer walks off the row range, or reading the rows in the wrong order.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Row Simulation with Bouncing Direction (Optimal, Intuitive)Optimal	`O(n)`	`O(n)`	Lead with this. It's the clearest mental model — literally write the characters into rows the way the diagram shows.	Read
2	Direct Index by Cycle Formula (O(1) Extra Space)	`O(n)`	`O(1)`	Offer when asked to avoid the row buffers or when numRows is huge. Frame it around the period 2·numRows − 2.	Read

The bouncing row index

How to read it:The current row walks down to numRows−1, flips direction, walks back up to 0, and repeats.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Row Simulation with Bouncing Direction (Optimal, Intuitive)

TimeO(n)SpaceO(n)

Lead with this. It's the clearest mental model — literally write the characters into rows the way the diagram shows.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Imagine actually writing the characters into the grid. You move down one row at a time, and when you hit the bottom you start moving up. What variable tracks which row you're on?

2Hint 2Explore hint

Keep one string buffer per row. Append each character to the current row, then update the row index by a step that is +1 going down and −1 going up.

3Hint 3Explore hint

Flip the step to +1 when you reach row 0 and to −1 when you reach row numRows−1. At the end, concatenate the row buffers top to bottom. Don't forget: if numRows == 1, just return s.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "PAYPALISHIRING", numRows = 3

Interactive diagram

Write diagonal, read horizontal

P (cur=0)

Active call / nodeSupporting contextReturned stateNot active

Characters are bucketed by row during the walk, then the rows are concatenated.

Final result"PAHNAPLSIIGYIR"

C · Code with teaching comments

solution.javaJava

Row Simulation with Bouncing Direction (Optimal, Intuitive) — optimal

4 teaching notes

1
public String convert(String s, int numRows) {
2
    // Guard the degenerate case — one row means the output is the input; bouncing logic
3
    // would otherwise misbehave.
4
    if (numRows == 1) {
5
        return s;
6
    }
7
    StringBuilder[] rows = new StringBuilder[numRows];
8
    for (int i = 0; i < numRows; i++) {
9
        rows[i] = new StringBuilder();
10
    }
11
    int cur = 0, step = 1;
12
    for (char c : s.toCharArray()) {
13
        // Drop the current character into whichever row the pen is on.
14
        rows[cur].append(c);
15
        if (cur == 0) {
16
            step = 1;
17
        } else if (cur == numRows - 1) {
18
            step = -1;
19
        }
20
        cur += step;
21
    }
22
    StringBuilder result = new StringBuilder();
23
    for (StringBuilder row : rows) {
24
        result.append(row);
25
    }
26
    return result.toString();
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7numRows = 1 — Returns s unchanged via the guard.Explore edge cases

Edge cases handled

numRows = 1Returns s unchanged via the guard.
numRows >= s.length()Pen never reaches the bottom; each early row gets one char, later rows stay empty. Concatenation still yields s reordered correctly.
s of length 2, numRows = 5Only rows 0 and 1 get a character; remaining rows are empty buffers and contribute nothing.

Pitfalls

Omitting the numRows == 1 guard — direction logic breaks or indexes row 1 that doesn't exist.
Flipping direction after moving instead of at the boundary — pointer walks out of range.
Reading rows in the wrong order or forgetting to concatenate all of them.
Using string += in a tight loop in Java instead of StringBuilder — quadratic time.

03.2

Approach 2 of 2

Direct Index by Cycle Formula (O(1) Extra Space)

TimeO(n)SpaceO(1)

Offer when asked to avoid the row buffers or when numRows is huge. Frame it around the period 2·numRows − 2.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the top row's indices in PAYPALISHIRING with 3 rows: 0, 4, 8, 12 — they differ by a fixed cycle. What is that cycle in terms of numRows?

2Hint 2Explore hint

One full down-and-up cycle covers 2·numRows − 2 characters. The first and last rows have exactly one character per cycle.

3Hint 3Explore hint

Middle rows have a second 'diagonal' character per cycle, located at index i + cycle − 2·row. Emit it when it's within bounds, and you never need row buffers.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "PAYPALISHIRING", numRows = 3

row 0

i = 0,4,8,12 → P,A,H,N

Stateresult = "PAHN"

Final result"PAHNAPLSIIGYIR"

C · Code with teaching comments

Reference implementation previewpublic String convert(String s, int numRows) { if (numRows == 1) { return s; } int n = s.length();Explore the full code

solution.javaJava

Direct Index by Cycle Formula (O(1) Extra Space) — reference

4 teaching notes

1
public String convert(String s, int numRows) {
2
    if (numRows == 1) {
3
        return s;
4
    }
5
    int n = s.length();
6
    // Characters per full down-and-up zigzag cycle — the period of the pattern.
7
    int cycle = 2 * numRows - 2;
8
    StringBuilder sb = new StringBuilder();
9
    for (int r = 0; r < numRows; r++) {
10
        // Each row's primary characters start at index r and recur every cycle.
11
        for (int i = r; i < n; i += cycle) {
12
            sb.append(s.charAt(i));
13
            // Only middle rows have the extra diagonal character per cycle.
14
            if (r != 0 && r != numRows - 1) {
15
                // Index of the ascending (diagonal) hit within the same cycle; emit
16
                // only if diag < n.
17
                int diag = i + cycle - 2 * r;
18
                if (diag < n) {
19
                    sb.append(s.charAt(diag));
20
                }
21
            }
22
        }
23
    }
24
    return sb.toString();
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7numRows = 1 — Guarded early return; cycle would be 0 and cause an infinite loop otherwise.Explore edge cases

Edge cases handled

numRows = 1Guarded early return; cycle would be 0 and cause an infinite loop otherwise.
numRows = 2cycle = 2; no middle rows, so it's two simple strided scans (even indices, then odd).
last partial cyclediag >= n on the final cycle of a middle row → the guard skips it, preventing an out-of-bounds.

Pitfalls

Forgetting the numRows == 1 guard — cycle becomes 0 and the loop never advances (infinite loop).
Emitting the diagonal char for edge rows — duplicates characters.
Omitting the diag < n bounds check — out-of-bounds on the final partial cycle.
Deriving the diagonal offset wrong — verify with a tiny example before trusting it.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String convert(String s, int numRows) { if (numRows == 1) { return s; } StringBuilder[] rows = new StringBuilder[numRows];Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the numRows == 1 guard

With one row, cur is always both 0 and the last index, so the bounce logic is contradictory; in the formula version cycle = 0 causes an infinite loop.

Explore the code comparison

Don't write this

rows = [''] * numRows
cur, step = 0, 1
for c in s:
    rows[cur] += c
    ...  # numRows == 1 never handled

Write this instead

if numRows == 1:
    return s
rows = [''] * numRows
cur, step = 0, 1
...

Flipping direction after overshooting

If you move first and then check, cur can become numRows (out of range) before you correct it.

Explore the code comparison

Don't write this

rows[cur].append(c);
cur += step;
if (cur == numRows) { step = -1; cur -= 2; }  // brittle correction

Write this instead

rows[cur].append(c);
if (cur == 0) step = 1;
else if (cur == numRows - 1) step = -1;
cur += step;

Emitting the diagonal for edge rows (formula version)

Rows 0 and numRows−1 have no second diagonal character; emitting one duplicates characters and corrupts the output.

Explore the code comparison

Don't write this

result.append(s[i])
diag = i + cycle - 2 * r
if diag < n:
    result.append(s[diag])  # wrong for r == 0 or r == numRows-1

Write this instead

result.append(s[i])
if r != 0 and r != numRows - 1:
    diag = i + cycle - 2 * r
    if diag < n:
        result.append(s[diag])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Row-bucket simulation with bouncing direction

Code pattern to memorize

if numRows == 1: return s
rows = [''] * numRows; cur = 0; step = 1
for c in s:
    rows[cur] += c
    if cur == 0: step = 1
    elif cur == numRows-1: step = -1
    cur += step
return ''.join(rows)

Rules to remember

1Guard `numRows == 1` first. With one row the zigzag is the original string; without the guard the direction never flips and step logic divides by a degenerate range.
2Flip direction AT the boundaries, not after overshooting. Set step = +1 when at row 0 and step = -1 when at the last row.
3Reading order is row-by-row, top to bottom — concatenate the buckets in order at the end.
4The cycle length is `2·numRows − 2` — the number of characters between two appearances in the same edge row. Useful for the O(1)-space math variant.
5The answer is read horizontally even though the string is written diagonally — that mismatch is the whole problem.

Use this pattern when

You must reorder characters according to a fixed geometric/positional pattern
The pattern repeats with a clear period (here, a zigzag cycle)
Direct simulation of 'place each item where it goes' is clear and linear
You can either bucket by destination or compute each destination index by formula

Choose another pattern when

The transformation is a simple reverse or rotation → no row buckets needed
There's no periodic geometry, just per-character mapping → plain map/transform
You need the inverse (zigzag string back to original) → different index math
numRows is huge relative to n → most rows are empty; the math variant avoids allocating them

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count and Say
Coming soon
Another build-a-string-by-simulation problem — generate each term from the previous.
Encode and Decode Strings
String construction with a positional scheme you must invert exactly.
Text Justification
Heavier simulation: lay characters out under positional rules, then read them back formatted.

Same pattern

←

Word Pattern

Continue · Next problem

Divisible Sum Pairs