Rotate Image

Search in Rotated Sorted Array

3Sum

Rotate an n x n matrix 90 degrees clockwise and return the rotated matrix.

You are given an `n x n` 2D matrix representing an image. Rotate the image by 90 degrees clockwise and return the rotated matrix. The judge checks the returned matrix, so you may build a new matrix or rotate in place and return it either way.

**Input / output**
- Input: `matrix: integer[][]`, always square (`n x n`)
- Output: `integer[][]`, the same matrix rotated 90 degrees clockwise

**Examples**
1. `matrix = [[1,2,3],[4,5,6],[7,8,9]]` returns `[[7,4,1],[8,5,2],[9,6,3]]`.
2. `matrix = [[1,2],[3,4]]` returns `[[3,1],[4,2]]`.
3. `matrix = [[1]]` returns `[[1]]`.

**Constraints**
- `n == matrix.length == matrix[i].length`
- `1 <= n <= 20`
- `-1,000 <= matrix[i][j] <= 1,000`

**Follow-up**
Can you rotate the matrix in place using only O(1) extra space, by first transposing and then reversing each row?

- You must rotate an `n x n` matrix 90 degrees clockwise.
- A naive approach allocates a brand new matrix and copies each cell to its rotated position — simple to reason about, but uses `O(n^2)` extra space.
- The interesting version of this problem does it **in place** with only `O(1)` extra space, which is what most interviewers are really asking for.

Understanding the Problem

- Rotating 90 degrees clockwise can be decomposed into two simpler, well-known in-place operations:
  1. **Transpose** the matrix (swap `matrix[i][j]` with `matrix[j][i]` for all `i < j`) — this flips the matrix across its main diagonal.
  2. **Reverse each row** — this mirrors every row horizontally.
- Doing both in sequence produces exactly the 90-degree clockwise rotation, using only the original array's memory.

The In-Place Trick: Transpose, Then Reverse

- After transposing, `matrix[i][j]` holds the original `matrix[j][i]`. The first column now reads top-to-bottom as the original first row read left-to-right.
- Reversing each row then flips that column's order, which is exactly what a clockwise rotation does: the original first row becomes the new last column, read top-to-bottom.
- Trace on `[[1,2,3],[4,5,6],[7,8,9]]`: transpose gives `[[1,4,7],[2,5,8],[3,6,9]]`; reversing each row gives `[[7,4,1],[8,5,2],[9,6,3]]` — the correct rotation.

Why Transpose + Reverse Works

Both the transpose and the row-reversal are `O(n^2)` (every cell is touched once), giving `O(n^2)` time and `O(1)` extra space overall — optimal, since you must write every one of the `n^2` output cells.

Final Solution (all languages)

- Transposing the full matrix (both `i < j` and `i > j`) undoes itself — only swap the upper triangle (`j > i`) once.
- Reversing columns instead of rows, or transposing across the anti-diagonal instead of the main diagonal, produces a counter-clockwise rotation or a flip instead of the required clockwise rotation.
- Follow-ups: how would you rotate 90 degrees counter-clockwise (reverse columns/rows in a different order)? How would you handle a non-square `m x n` matrix, where true in-place rotation isn't possible without extra bookkeeping?