Zigzag Conversion

MediumStrings · Simulation · Index Math🧩 String Manipulation LeetCode #6 ↗Updated Oct 30, 2026

Problem

Lay the characters of s out on numRows rows in a zigzag: go straight down row by row, then diagonally up to the top, and repeat. Return the string you get by reading the rows top to bottom, each left to right.

Inputs = "ABCDEFGHI", numRows = 3Output"AEIBDFHCG"

Inputs = "ABCDEFGHIJ", numRows = 4Output"AGBFHCEIDJ"

Inputs = "XY", numRows = 1Output"XY"

1 ≤ s.length ≤ 1000 · s has English letters, ',' and '.' · 1 ≤ numRows ≤ 1000

Try it yourself

Java

class Solution {
    public String convert(String s, int numRows) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The pattern repeats every cycle = 2·numRows − 2 characters. Inside each cycle, row r gets offset r (going down) and, for middle rows, offset cycle − r (coming up) — so each row can be read straight from s by index math.

PatternString Manipulation

Instinct Reading, comparing or rebuilding text character by character? Walk indices on a char[] and build output with a StringBuilder, never with + in a loop.

Memory hack Chars in an array, pointers on the ends, builder at the back - strings are just arrays wearing a costume.

Open the String Manipulation guide →

Approaches

Brute ForceDraw the Grid

Time O(numRows · n)Space O(numRows · n)

Literally simulate the drawing on a numRows × n char grid: move down placing characters, and at the bottom move up-right one cell per character until the top. Then scan the grid row by row, skipping empty cells.

Java

public String convert(String s, int numRows) {
    int n = s.length();
    if (numRows == 1 || numRows >= n) return s;
    char[][] grid = new char[numRows][n]; // '\0' marks an empty cell
    int row = 0, col = 0;
    boolean down = true;
    for (int i = 0; i < n; i++) {
        grid[row][col] = s.charAt(i);
        if (down) {
            if (row == numRows - 1) { down = false; row--; col++; }
            else row++;
        } else {
            if (row == 0) { down = true; row++; }
            else { row--; col++; }
        }
    }
    StringBuilder sb = new StringBuilder(n);
    for (char[] line : grid)
        for (char ch : line) if (ch != '\0') sb.append(ch);
    return sb.toString();
}

Mirrors the picture exactly, but the grid is mostly empty cells.

BetterOne Buffer per Row

Time O(n)Space O(n)

Columns do not matter for the output, only which row each character lands in. Keep a StringBuilder per row and a direction that flips at the top and bottom rows; finally concatenate the rows.

Java

public String convert(String s, int numRows) {
    if (numRows == 1 || numRows >= s.length()) return s;
    StringBuilder[] rows = new StringBuilder[numRows];
    for (int r = 0; r < numRows; r++) rows[r] = new StringBuilder();
    int row = 0, step = 1; // +1 going down, -1 going up
    for (char ch : s.toCharArray()) {
        rows[row].append(ch);
        if (row == 0) step = 1;
        else if (row == numRows - 1) step = -1;
        row += step;
    }
    StringBuilder out = new StringBuilder(s.length());
    for (StringBuilder r : rows) out.append(r);
    return out.toString();
}

Clean linear simulation — usually enough, but allocates a buffer per row.

OptimalRead Each Row by Cycle Arithmetic

Time O(n)Space O(1) extra (output only)

With cycle = 2·numRows − 2, row r holds indices k + r for k = 0, cycle, 2·cycle, …, and middle rows also hold k + cycle − r. Visiting rows in order and appending those indices writes the answer directly, each character exactly once.

Java

public String convert(String s, int numRows) {
    int n = s.length();
    if (numRows == 1 || numRows >= n) return s;
    int cycle = 2 * numRows - 2;
    StringBuilder sb = new StringBuilder(n);
    for (int r = 0; r < numRows; r++) {
        for (int k = 0; k + r < n; k += cycle) {
            sb.append(s.charAt(k + r)); // vertical (downward) character
            int diag = k + cycle - r;   // diagonal (upward) character
            if (r != 0 && r != numRows - 1 && diag < n) sb.append(s.charAt(diag));
        }
    }
    return sb.toString();
}

Dry runs = "ABCDEFGHI", numRows = 3

r taken by current row changed

setup
A

B

C

D

E

F

G

H

I

rows=3, cycle=4
r=0
A
r
B

C

D

E
r
F

G

H

I
r
k+0 → AEI
r=1
A

B
r
C

D
r
E

F
r
G

H
r
I

k+1, k+3 → BDFH
r=2
A

B

C
r
D

E

F

G
r
H

I

k+2 → CG ✔

Single output buffer, no simulation state — the tightest solution.

Pro tip

Handle numRows == 1 first — otherwise cycle is 0 and the inner loop never advances.

At a glance

Level	Approach	Time	Space
Brute Force	Draw the Grid	`O(numRows · n)`	`O(numRows · n)`
Better	One Buffer per Row	`O(n)`	`O(n)`
Optimal	Read Each Row by Cycle Arithmetic	`O(n)`	`O(1) extra (output only)`

Common pitfalls

numRows == 1: the direction flip or cycle = 0 causes an infinite loop.
Adding the diagonal character on the top or bottom row — it would be counted twice.
Flipping direction after moving instead of before — the row index goes out of range.

Interview tips

Draw a small example and mark indices to discover cycle = 2·numRows − 2.
Start with the row-buffer simulation, then derive the index formula from it.
Test numRows = 1, 2 and ≥ n explicitly.

Pattern

Periodic index mapping → when a layout repeats with a fixed period, compute positions instead of simulating.

My notes saved in this browser