LeetCode 6 - Zigzag Conversion

The problem asks us to transform a string into a zigzag pattern across a fixed number of rows, then read the characters row by row to produce the final result.

leetcodemediumstring

LeetCode Problem 6

Difficulty: 🟡 Medium
Topics: String

Solution

Problem Understanding

The problem asks us to transform a string into a zigzag pattern across a fixed number of rows, then read the characters row by row to produce the final result.

For example, if the input string is "PAYPALISHIRING" and the number of rows is 3, the zigzag layout looks like this:

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

The characters are written by moving vertically downward through the rows, then diagonally upward, repeating this motion until all characters are placed. After building this pattern, we read each row from left to right and concatenate them together.

The expected output for this example is:

"PAHNAPLSIIGYIR"

The input consists of:

  • A string s
  • An integer numRows

The output is a new string formed by reading the zigzag pattern row by row.

The constraints are relatively small:

  • 1 <= s.length <= 1000
  • 1 <= numRows <= 1000

Since the maximum string length is only 1000, an O(n) or O(n * numRows) solution is completely acceptable. However, the problem is mainly about correctly simulating the zigzag traversal rather than dealing with performance limits.

Several edge cases are important:

  • If numRows == 1, there is no zigzag movement. The string remains unchanged.
  • If numRows >= len(s), every character effectively occupies its own row before any upward diagonal movement can happen, so the output is also the original string.
  • Strings with very small lengths can expose incorrect direction-switching logic.
  • Incorrect handling of row boundaries can easily lead to index errors or misplaced characters.

The core challenge is managing the movement between rows correctly.

Approaches

Brute Force Approach

A brute-force approach would explicitly build the entire two-dimensional zigzag matrix.

We could estimate the number of columns needed, create a grid filled with empty characters, and then simulate the downward and upward traversal while placing characters into the grid. After filling the matrix, we would scan it row by row and collect all non-empty characters.

This approach works because it directly models the zigzag structure exactly as described in the problem statement. However, it wastes space because most cells in the matrix remain empty, especially during diagonal movements.

The implementation also becomes unnecessarily complicated because we must carefully manage row and column movement while avoiding unused positions.

Optimal Approach

The key observation is that we do not actually need the full matrix.

The final answer only depends on the characters collected in each row. Instead of storing every position in a two-dimensional grid, we can maintain a separate string builder for each row.

As we iterate through the input string:

  • We append each character to the current row
  • We move downward through the rows
  • Once we reach the bottom row, we reverse direction
  • Then we move upward diagonally
  • Once we reach the top row, we reverse direction again

This simulates the zigzag traversal directly while storing only the necessary data.

This approach is both simpler and more memory-efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Builds an explicit zigzag matrix with many unused cells
Optimal O(n) O(n) Simulates row traversal directly using row builders

Algorithm Walkthrough

  1. Handle the trivial edge case first.

If numRows == 1 or numRows >= len(s), return the original string immediately. In these cases, no zigzag transformation occurs. 2. Create storage for each row.

We maintain an array where each element represents one row of the zigzag pattern. Each row stores the characters assigned to it. 3. Initialize traversal state.

We track:

  • current_row, the row currently receiving characters
  • direction, which determines whether we are moving downward or upward

Initially:

  • current_row = 0
  • direction = 1, meaning downward movement
  1. Process each character in the string.

For every character:

  • Append it to the current row
  • Update the direction if we hit the top or bottom row
  • Move to the next row according to the direction
  1. Reverse direction at boundaries.

When we reach:

  • The bottom row, switch direction upward
  • The top row, switch direction downward

This creates the zigzag traversal pattern. 6. Combine all rows.

After processing all characters, concatenate every row together to form the final answer.

Why it works

At every step, the algorithm maintains the invariant that each character is appended to exactly the same row it would occupy in the actual zigzag layout.

The direction-switching logic guarantees that traversal follows the required pattern:

  • Straight downward movement
  • Then diagonal upward movement
  • Then repeating

Since characters are stored row by row during traversal, concatenating the rows at the end produces exactly the required output.

Python Solution

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s

        rows = [""] * numRows

        current_row = 0
        direction = 1

        for char in s:
            rows[current_row] += char

            if current_row == 0:
                direction = 1
            elif current_row == numRows - 1:
                direction = -1

            current_row += direction

        return "".join(rows)

The implementation begins by handling the edge case where zigzag conversion is unnecessary. This avoids incorrect direction changes and simplifies the rest of the logic.

The rows array stores the characters belonging to each zigzag row. Each entry accumulates characters as we traverse the string.

The variable current_row tracks where the next character should be placed. The direction variable controls movement:

  • 1 means moving downward
  • -1 means moving upward

For every character:

  • The character is appended to the current row
  • We check whether we reached the top or bottom
  • If so, we reverse direction
  • Then we move to the next row

Finally, "".join(rows) concatenates all rows into the required answer.

Go Solution

func convert(s string, numRows int) string {
    if numRows == 1 || numRows >= len(s) {
        return s
    }

    rows := make([]string, numRows)

    currentRow := 0
    direction := 1

    for _, char := range s {
        rows[currentRow] += string(char)

        if currentRow == 0 {
            direction = 1
        } else if currentRow == numRows-1 {
            direction = -1
        }

        currentRow += direction
    }

    result := ""

    for _, row := range rows {
        result += row
    }

    return result
}

The Go implementation follows the same logic as the Python version.

A slice of strings is used to store row contents. Since Go strings are immutable, concatenation creates new strings internally, which is acceptable given the small constraint size.

The loop iterates over Unicode runes using range, ensuring proper character handling.

The direction-switching logic is identical:

  • Move downward until the last row
  • Reverse upward until the first row
  • Repeat

Finally, all rows are concatenated into the result string.

Worked Examples

Example 1

Input:

s = "PAYPALISHIRING"
numRows = 3

Initial state:

Variable Value
rows ["", "", ""]
current_row 0
direction 1

Processing steps:

Character Row Before Insert Rows After Insert Direction Next Row
P 0 ["P", "", ""] down 1
A 1 ["P", "A", ""] down 2
Y 2 ["P", "A", "Y"] up 1
P 1 ["P", "AP", "Y"] up 0
A 0 ["PA", "AP", "Y"] down 1
L 1 ["PA", "APL", "Y"] down 2
I 2 ["PA", "APL", "YI"] up 1
S 1 ["PA", "APLS", "YI"] up 0
H 0 ["PAH", "APLS", "YI"] down 1
I 1 ["PAH", "APLSI", "YI"] down 2
R 2 ["PAH", "APLSI", "YIR"] up 1
I 1 ["PAH", "APLSII", "YIR"] up 0
N 0 ["PAHN", "APLSII", "YIR"] down 1
G 1 ["PAHN", "APLSIIG", "YIR"] down 2

Final result:

"PAHNAPLSIIGYIR"

Example 2

Input:

s = "PAYPALISHIRING"
numRows = 4

Zigzag layout:

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

Rows collected during traversal:

Row Characters
0 PIN
1 ALSIG
2 YAHR
3 PI

Final result:

"PINALSIGYAHRPI"

Example 3

Input:

s = "A"
numRows = 1

Since there is only one row, the string is returned unchanged.

Output:

"A"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed exactly once
Space O(n) The row storage collectively stores all characters

The algorithm performs a single pass through the input string. Every character is appended once and later joined once, so the total work is linear in the size of the input.

The additional memory usage comes from storing the row strings, which together contain exactly n characters.

Test Cases

solution = Solution()

assert solution.convert("PAYPALISHIRING", 3) == "PAHNAPLSIIGYIR"  # standard example with 3 rows
assert solution.convert("PAYPALISHIRING", 4) == "PINALSIGYAHRPI"  # standard example with 4 rows
assert solution.convert("A", 1) == "A"  # single character
assert solution.convert("AB", 1) == "AB"  # one row means unchanged
assert solution.convert("AB", 2) == "AB"  # exactly two rows
assert solution.convert("ABC", 5) == "ABC"  # numRows larger than string length
assert solution.convert("HELLOWORLD", 2) == "HLOOLELWRD"  # alternating rows
assert solution.convert("ABCDE", 4) == "ABCED"  # incomplete final zigzag cycle
assert solution.convert("THISISAZIGZAG", 3) == "TIIGHSZAZAISG"  # repeated zigzag cycles
assert solution.convert("", 1) == ""  # empty string edge case if allowed outside constraints
Test Why
"PAYPALISHIRING", 3 Verifies standard zigzag behavior
"PAYPALISHIRING", 4 Verifies diagonal traversal logic
"A", 1 Smallest valid input
"AB", 1 Tests no-zigzag condition
"AB", 2 Tests minimal non-trivial zigzag
"ABC", 5 Tests when rows exceed string length
"HELLOWORLD", 2 Tests alternating up/down movement
"ABCDE", 4 Tests partial final cycle
"THISISAZIGZAG", 3 Tests multiple direction reversals
"", 1 Defensive test outside official constraints

Edge Cases

Single Row

When numRows == 1, there is no downward and upward movement. A naive implementation that blindly applies direction changes may incorrectly attempt to move between nonexistent rows.

The solution handles this immediately by returning the original string before any traversal logic begins.

More Rows Than Characters

If numRows >= len(s), every character would simply occupy a separate row before any diagonal movement could occur.

Without special handling, some implementations may incorrectly reverse direction or access invalid row indices. Returning the original string avoids these issues entirely.

Direction Switching at Boundaries

One of the most common bugs is incorrect direction reversal when reaching the first or last row.

For example, after reaching the bottom row, the algorithm must immediately switch to upward movement before processing the next character. Failing to do this causes index errors or duplicated rows.

The implementation solves this by checking boundary conditions immediately after inserting each character and updating the direction before moving to the next row.