# LeetCode 48: Rotate Image

## Problem Restatement

We are given an `n x n` matrix representing an image.

We need to rotate the matrix by `90` degrees clockwise.

The rotation must be done in-place. That means we must modify the input matrix directly and must not allocate another matrix for the rotated result. The official problem states this in-place requirement directly.

Example:

```python
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
```

After rotation:

```python
[
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3],
]
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | An `n x n` integer matrix |
| Output | No returned value |
| Operation | Modify `matrix` in-place |
| Rotation | `90` degrees clockwise |

Function shape:

```python
def rotate(matrix: list[list[int]]) -> None:
    ...
```

## First Thought: Use Another Matrix

A simple way is to create a new matrix.

For every original cell:

```python
matrix[i][j]
```

its rotated position is:

```python
matrix[j][n - 1 - i]
```

So we could copy values into a new matrix.

But the problem requires in-place rotation, so this approach violates the space requirement.

We need to rearrange the original matrix itself.

## Key Insight

A `90` degree clockwise rotation can be done with two in-place operations:

1. Transpose the matrix.
2. Reverse each row.

Transpose means swapping across the main diagonal.

For example:

```python
[
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
```

After transpose:

```python
[
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9],
]
```

Then reverse each row:

```python
[
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3],
]
```

This is the required clockwise rotation.

## Algorithm

Let:

```python
n = len(matrix)
```

First, transpose the matrix.

For every pair of indices where `j > i`, swap:

```python
matrix[i][j], matrix[j][i]
```

Then reverse each row in-place.

For every row:

```python
row.reverse()
```

The matrix is now rotated clockwise.

## Walkthrough

Use:

```python
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
```

First transpose.

Swap `matrix[0][1]` with `matrix[1][0]`:

```python
[
    [1, 4, 3],
    [2, 5, 6],
    [7, 8, 9],
]
```

Swap `matrix[0][2]` with `matrix[2][0]`:

```python
[
    [1, 4, 7],
    [2, 5, 6],
    [3, 8, 9],
]
```

Swap `matrix[1][2]` with `matrix[2][1]`:

```python
[
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9],
]
```

Now reverse each row:

```python
[
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3],
]
```

## Correctness

Consider an original element at position `(i, j)`.

After transposition, it moves to:

```python
(j, i)
```

After reversing each row, the column index `i` becomes:

```python
n - 1 - i
```

So the element moves from:

```python
(i, j)
```

to:

```python
(j, n - 1 - i)
```

That is exactly the position of `(i, j)` after a `90` degree clockwise rotation.

Since every element is moved according to the clockwise rotation rule, the final matrix is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | Every matrix cell is touched a constant number of times |
| Space | `O(1)` | The matrix is modified in-place |

## Implementation

```python
class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)

        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        for row in matrix:
            row.reverse()
```

## Code Explanation

We first compute the matrix size:

```python
n = len(matrix)
```

Then we transpose the matrix:

```python
for i in range(n):
    for j in range(i + 1, n):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
```

The inner loop starts at `i + 1` so we only swap cells above the main diagonal.

This avoids swapping the same pair twice.

Then we reverse each row:

```python
for row in matrix:
    row.reverse()
```

After these two operations, the matrix has been rotated `90` degrees clockwise in-place.

## Testing

```python
def run_tests():
    s = Solution()

    matrix = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]
    s.rotate(matrix)
    assert matrix == [
        [7, 4, 1],
        [8, 5, 2],
        [9, 6, 3],
    ]

    matrix = [
        [5, 1, 9, 11],
        [2, 4, 8, 10],
        [13, 3, 6, 7],
        [15, 14, 12, 16],
    ]
    s.rotate(matrix)
    assert matrix == [
        [15, 13, 2, 5],
        [14, 3, 4, 1],
        [12, 6, 8, 9],
        [16, 7, 10, 11],
    ]

    matrix = [[1]]
    s.rotate(matrix)
    assert matrix == [[1]]

    matrix = [
        [1, 2],
        [3, 4],
    ]
    s.rotate(matrix)
    assert matrix == [
        [3, 1],
        [4, 2],
    ]

    print("all tests passed")

run_tests()
```

| Test | Expected | Reason |
|---|---|---|
| `3 x 3` matrix | Rotated matrix | Standard odd-sized case |
| `4 x 4` matrix | Rotated matrix | Standard even-sized case |
| `1 x 1` matrix | Same matrix | Single element stays fixed |
| `2 x 2` matrix | Rotated matrix | Smallest non-trivial square |