LeetCode 6: Zigzag Conversion

Problem Restatement

We are given:

• a string s
• an integer numRows

We write the characters of the string in a zigzag pattern across multiple rows.

Then we read the rows from top to bottom.

The result is a new string.

The official LeetCode statement uses this example: (leetcode.com)

PAYPALISHIRING

with:

numRows = 3

becomes:

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

Reading row by row gives:

PAHNAPLSIIGYIR

That is the required output.

Input and Output

Example function shape:

def convert(s: str, numRows: int) -> str:
    ...

Examples

Example 1:

s = "PAYPALISHIRING"
numRows = 3

Pattern:

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

Output:

"PAHNAPLSIIGYIR"

Example 2:

s = "PAYPALISHIRING"
numRows = 4

Pattern:

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

Output:

"PINALSIGYAHRPI"

Example 3:

s = "A"
numRows = 1

Output:

"A"

First Thought: Build the Entire Grid

One possible idea:

1. Create a large 2D matrix.
2. Simulate writing characters into the zigzag shape.
3. Read the matrix row by row.

This works conceptually, but most matrix cells stay empty.

For example:

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

Many spaces are unused.

Building the full grid wastes memory and complicates indexing.

Key Insight

We do not actually need the 2D grid.

We only need to know:

• which row the current character belongs to
• whether we are moving downward or upward

We can maintain one string for each row.

As we scan the input string:

1. Append the current character to the current row.
2. Move:
   • downward
   • or upward diagonally
3. Repeat until all characters are processed.

At the end, concatenate all rows together.

Visual Walkthrough

Use:

s = "PAYPALISHIRING"
numRows = 3

Create rows:

row0 = ""
row1 = ""
row2 = ""

Start at row 0.

Direction is downward.

Read:

P

Add to row 0:

row0 = "P"

Move down to row 1.

Read:

A

Add to row 1:

row1 = "A"

Move down to row 2.

Read:

Y

Add to row 2:

row2 = "Y"

Now we reached the bottom row.

Direction changes upward.

Next character:

P

Add to row 1.

Continue the same process until the string ends.

Final rows:

row0 = "PAHN"
row1 = "APLSIIG"
row2 = "YIR"

Concatenate:

"PAHNAPLSIIGYIR"

Algorithm

Handle the special case first:

If:

numRows == 1

then the zigzag has only one row, so the output equals the input.

Otherwise:

1. Create one string builder per row.
2. Start at row 0.
3. Maintain direction:
   • downward
   • upward
4. For each character:
   • append it to the current row
   • update the row index
5. Join all rows together.

Correctness

At every step, the algorithm stores each character in exactly the row where it appears in the zigzag pattern.

The direction changes only at:

• the top row
• the bottom row

This exactly matches the zigzag movement defined by the problem.

The algorithm processes characters in the same order they are written into the pattern.

Then it concatenates rows from top to bottom, which matches the required reading order.

Therefore the produced string is exactly the zigzag conversion defined in the problem statement.

Complexity

Where:

n = len(s)

Implementation

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)

Code Explanation

Special case:

if numRows == 1 or numRows >= len(s):
    return s

If there is only one row, no zigzag movement exists.

We create storage for every row:

rows = [""] * numRows

current_row tracks where the next character goes:

current_row = 0

direction controls movement:

For every character:

rows[current_row] += char

Then update direction at boundaries.

Top row:

if current_row == 0:
    direction = 1

Bottom row:

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

Move to the next row:

current_row += direction

Finally combine all rows:

return "".join(rows)

Testing

def run_tests():
    s = Solution()

    assert s.convert("PAYPALISHIRING", 3) == "PAHNAPLSIIGYIR"
    assert s.convert("PAYPALISHIRING", 4) == "PINALSIGYAHRPI"
    assert s.convert("A", 1) == "A"
    assert s.convert("AB", 1) == "AB"
    assert s.convert("ABC", 2) == "ACB"
    assert s.convert("ABCDE", 4) == "ABCED"

    print("all tests passed")

run_tests()