Zigzag Conversion

Medium
1199.

Zigzag Conversion

Zigzag Conversion is a medium coding problem on strings and simulation, asked in Amazon, Microsoft and Adobe interviews.

Lay the characters of s out on numRows rows in a zigzag: the first character goes on row 0, then each next character goes one row lower until the bottom row is reached, then one row higher (moving one column right each step) until row 0 is reached again, and so on.

For s = "CODEKAIRO.ROCKS" and numRows = 3 the layout is:

C   K   O   C
O E A R . O K
D   I   R   S

Return the string obtained by reading the rows top to bottom, each row left to right. With a single row the text is unchanged.

Example 1

Input
s = "CODEKAIRO.ROCKS", numRows = 3
Output
"CKOCOEAR.OKDIRS"
Explanation
Rows read `CKOC`, `OEAR.OK` and `DIRS`.

Example 2

Input
s = "ZigZag,Fun", numRows = 4
Output
"Z,igFgauZn"

Example 3

Input
s = "A", numRows = 1
Output
"A"

Constraints

  • 1 <= s.length <= 1000
  • s consists of English letters, ',' and '.'
  • 1 <= numRows <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var zigzagConvert = function(s, numRows) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Zigzag Conversion — Solution in Python, Java & C++

Zigzag Conversion solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Zigzag Conversion is a medium coding problem on strings and simulation, asked in Amazon, Microsoft and Adobe interviews.

  • Difficulty: Medium
  • Topics: Strings, Simulation
  • Asked at: Amazon, Microsoft, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Lay the characters of s out on numRows rows in a zigzag: the first character goes on row 0, then each next character goes one row lower until the bottom row is reached, then one row higher (moving one column right each step) until row 0 is reached again, and so on.

For s = "CODEKAIRO.ROCKS" and numRows = 3 the layout is:

C   K   O   C
O E A R . O K
D   I   R   S

Return the string obtained by reading the rows top to bottom, each row left to right. With a single row the text is unchanged.

Example 1

Input: s = "CODEKAIRO.ROCKS", numRows = 3
Output: "CKOCOEAR.OKDIRS"
Explanation: Rows read `CKOC`, `OEAR.OK` and `DIRS`.

Example 2

Input: s = "ZigZag,Fun", numRows = 4
Output: "Z,igFgauZn"

Example 3

Input: s = "A", numRows = 1
Output: "A"

Constraints

  • 1 <= s.length <= 1000
  • s consists of English letters, ',' and '.'
  • 1 <= numRows <= 1000

Hints for Zigzag Conversion

  1. Hint 1

    You do not need a 2-D grid: only the order of characters within each row matters.

  2. Hint 2

    The pattern repeats every 2 * numRows - 2 characters (one trip down and back up).

  3. Hint 3

    Row r takes index j for j = r, r + cycle, …, and every middle row also takes j + cycle - 2r from the upward stroke.

How to solve Zigzag Conversion

The zigzag is periodic with period cycle = 2·numRows − 2, so every row can be read straight from s by index arithmetic instead of drawing the picture.

Approach

  1. If numRows is 1 or at least s.length, return s unchanged — no character ever moves.
  2. Set cycle = 2·numRows − 2.
  3. For each row r from 0 to numRows − 1, walk j = r, r + cycle, r + 2·cycle, … while j < n and append s[j].
  4. For a middle row (0 < r < numRows − 1), after s[j] also append s[j + cycle − 2r] when that index exists — it is the character the upward diagonal drops on row r within the same period.

Why it works

Within one period the column goes down through rows 0…numRows−1 (offsets 0…numRows−1) and back up through rows numRows−2…1 (offsets numRows…cycle−1). Row r therefore receives offset r on the way down and offset cycle − r on the way up, and the two coincide only for the top and bottom rows. Reading periods in order, and within a period the down offset before the up one, gives each row's characters left to right.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • numRows = 1 makes the cycle 0 — handle it first or the loop never advances.
  • Top and bottom rows get one character per period, not two; adding the up-stroke there duplicates characters.
  • Building an actual numRows × n grid works but wastes memory when numRows is large.

Reference solution

Python

def zigzagConvert(s: str, numRows: int) -> str:
    n = len(s)
    if numRows == 1 or numRows >= n:
        return s
    cycle = 2 * numRows - 2
    out = []
    for r in range(numRows):
        j = r
        while j < n:
            out.append(s[j])
            k = j + cycle - 2 * r
            if 0 < r < numRows - 1 and k < n:
                out.append(s[k])
            j += cycle
    return "".join(out)

Java

public static String zigzagConvert(String s, int numRows) {
    int n = s.length();
    if (numRows == 1 || numRows >= n) return s;
    int cycle = 2 * numRows - 2;
    StringBuilder sb = new StringBuilder();
    for (int r = 0; r < numRows; r++) {
        for (int j = r; j < n; j += cycle) {
            sb.append(s.charAt(j));
            int k = j + cycle - 2 * r;
            if (r > 0 && r < numRows - 1 && k < n) sb.append(s.charAt(k));
        }
    }
    return sb.toString();
}

C++

string zigzagConvert(string s, int numRows) {
    int n = (int)s.size();
    if (numRows == 1 || numRows >= n) return s;
    int cycle = 2 * numRows - 2;
    string out;
    for (int r = 0; r < numRows; r++) {
        for (int j = r; j < n; j += cycle) {
            out.push_back(s[j]);
            int k = j + cycle - 2 * r;
            if (r > 0 && r < numRows - 1 && k < n) out.push_back(s[k]);
        }
    }
    return out;
}

JavaScript

var zigzagConvert = function(s, numRows) {
    var n = s.length;
    if (numRows === 1 || numRows >= n) return s;
    var cycle = 2 * numRows - 2;
    var out = [];
    for (var r = 0; r < numRows; r++) {
        for (var j = r; j < n; j += cycle) {
            out.push(s[j]);
            var k = j + cycle - 2 * r;
            if (r > 0 && r < numRows - 1 && k < n) out.push(s[k]);
        }
    }
    return out.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings