# 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](https://leetcode.com/problems/zigzag-conversion/?utm_source=chatgpt.com))

```text
PAYPALISHIRING
```

with:

```text
numRows = 3
```

becomes:

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

Reading row by row gives:

```text
PAHNAPLSIIGYIR
```

That is the required output.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` and an integer `numRows` |
| Output | The zigzag-converted string |
| Constraint | `1 <= s.length <= 1000` |
| Constraint | `1 <= numRows <= 1000` |

Example function shape:

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

## Examples

Example 1:

```text
s = "PAYPALISHIRING"
numRows = 3
```

Pattern:

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

Output:

```text
"PAHNAPLSIIGYIR"
```

Example 2:

```text
s = "PAYPALISHIRING"
numRows = 4
```

Pattern:

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

Output:

```text
"PINALSIGYAHRPI"
```

Example 3:

```text
s = "A"
numRows = 1
```

Output:

```text
"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:

```text
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:

```text
s = "PAYPALISHIRING"
numRows = 3
```

Create rows:

```text
row0 = ""
row1 = ""
row2 = ""
```

Start at row `0`.

Direction is downward.

Read:

```text
P
```

Add to row `0`:

```text
row0 = "P"
```

Move down to row `1`.

Read:

```text
A
```

Add to row `1`:

```text
row1 = "A"
```

Move down to row `2`.

Read:

```text
Y
```

Add to row `2`:

```text
row2 = "Y"
```

Now we reached the bottom row.

Direction changes upward.

Next character:

```text
P
```

Add to row `1`.

Continue the same process until the string ends.

Final rows:

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

Concatenate:

```text
"PAHNAPLSIIGYIR"
```

## Algorithm

Handle the special case first:

If:

```text
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each character is processed once |
| Space | `O(n)` | Rows store all characters |

Where:

```text
n = len(s)
```

## Implementation

```python
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:

```python
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:

```python
rows = [""] * numRows
```

`current_row` tracks where the next character goes:

```python
current_row = 0
```

`direction` controls movement:

| Value | Meaning |
|---|---|
| `1` | Move downward |
| `-1` | Move upward |

For every character:

```python
rows[current_row] += char
```

Then update direction at boundaries.

Top row:

```python
if current_row == 0:
    direction = 1
```

Bottom row:

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

Move to the next row:

```python
current_row += direction
```

Finally combine all rows:

```python
return "".join(rows)
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| Standard 3-row example | Official example |
| Standard 4-row example | Diagonal movement check |
| Single character | Minimum size |
| One row | No zigzag behavior |
| Two rows | Simplest real zigzag |
| Many rows relative to string | Boundary behavior |