Zigzag Conversion

Medium Arrays & Hashing Simulation Original on LeetCode

Reported atPayPalZoho

Zigzag Conversion is a medium arrays & hashing problem solved with the simulation pattern. The best approach, optimal (one buffer per row), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (draw the zigzag on a grid) up.

Problem

Write the characters of a string s in a zigzag over numRows rows: go straight down from row 0 to row numRows - 1, then diagonally back up to row 0, then down again, and so on, one character per position. For example, "ALGORITHMS" on 3 rows looks like this:

A   R   M
L O I H S
G   T

Return the string you get by reading the zigzag row by row, left to right (here "ARMLOIHSGT").

Examples

Example 1

Input
s = "ALGORITHMS", numRows = 3
Output
"ARMLOIHSGT"
Why
Written in a zigzag the rows are A, R, M (row 0), L, O, I, H, S (row 1) and G, T (row 2). Reading row by row gives ARM + LOIHS + GT.

Example 2

Input
s = "WAVELENGTH", numRows = 4
Output
"WNAEGVLTEH"
Why
Row 0 gets W, N; row 1 gets A, E, G; row 2 gets V, L, T; row 3 gets E, H.

Example 3

Input
s = "OK", numRows = 5
Output
"OK"
Why
With more rows than characters, each character sits on its own row and the order does not change.

Constraints

  • 1 <= s.length <= 1000
  • 1 <= numRows <= 1000
  • s contains English letters (both cases), , and ..

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (draw the zigzag on a grid)O(numRows · n)O(numRows · n)
Optimal (one buffer per row)O(n)O(n)

1Brute force (draw the zigzag on a grid)

TimeO(numRows · n)The final scan reads every cell of the grid.
SpaceO(numRows · n)The grid has numRows rows and up to n columns.

Place the characters on a 2D grid exactly as they would be drawn: go straight down a column, then diagonally up and to the right, and repeat. Then read the grid row by row, skipping empty cells.

  1. If numRows == 1, return s.
  2. grid = numRows × n cells; r = 0, c = 0, goingDown = true.
  3. For each char: grid[r][c] = char. If goingDown and r == numRows - 1, switch to going up; if going up and r == 0, switch to going down. Moving down: r++; moving up: r--, c++.
  4. Concatenate non-empty cells row by row.
class Solution {
    public String convert(String s, int numRows) {
        int n = s.length();
        if (numRows == 1 || numRows >= n) return s;
        char[][] grid = new char[numRows][n];
        int r = 0, c = 0;
        boolean down = true;
        for (int i = 0; i < n; i++) {
            grid[r][c] = s.charAt(i);
            if (down && r == numRows - 1) down = false;
            else if (!down && r == 0) down = true;
            if (down) r++;
            else { r--; c++; }
        }
        StringBuilder sb = new StringBuilder();
        for (char[] row : grid)
            for (char ch : row)
                if (ch != 0) sb.append(ch);
        return sb.toString();
    }
}

2Optimal (one buffer per row)

TimeO(n)Each character is appended once and copied once into the result.
SpaceO(n)The row buffers together hold n characters.

Columns do not matter for the answer, only which row each character lands on. Keep a string buffer per row and a current row that bounces between 0 and numRows - 1; append each character to its row's buffer and finally join the buffers.

  1. If numRows == 1 or numRows >= n, return s.
  2. rows = numRows empty buffers; row = 0, step = 1.
  3. For each char: append to rows[row]; if row == 0 set step = 1, if row == numRows - 1 set step = -1; row += step.
  4. Join all buffers in order.
class Solution {
    public String convert(String s, int numRows) {
        int n = s.length();
        if (numRows == 1 || numRows >= n) return s;
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
        int row = 0, step = 1;
        for (int i = 0; i < n; i++) {
            rows[row].append(s.charAt(i));
            if (row == 0) step = 1;
            else if (row == numRows - 1) step = -1;
            row += step;
        }
        StringBuilder out = new StringBuilder();
        for (StringBuilder sb : rows) out.append(sb);
        return out.toString();
    }
}

Edge cases to test

  • numRows = 1: the string is unchanged (there is no bouncing)
  • numRows >= s.length: the string is unchanged
  • numRows = 2: characters alternate between the two rows

Hints

Hint 1

Simulate it: walk down the rows, then back up, placing one character per step. When do you change direction?

Hint 2

You never need the column positions. Keep one buffer per row and append each character to the row you are currently on.

FAQ

What is the best time complexity for Zigzag Conversion?

Optimal (one buffer per row) runs in O(n) time and O(n) extra space. Each character is appended once and copied once into the result.

Which pattern does Zigzag Conversion use?

It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, Integer to English Words, String to Integer (atoi).

Is there a brute force solution for Zigzag Conversion?

Yes. Brute force (draw the zigzag on a grid) takes O(numRows · n) time and O(numRows · n) space. Place the characters on a 2D grid exactly as they would be drawn: go straight down a column, then diagonally up and to the right, and repeat.

Which edge cases should I test for Zigzag Conversion?

numRows = 1: the string is unchanged (there is no bouncing); numRows = s.length: the string is unchanged; numRows = 2: characters alternate between the two rows.