Rotate Image

Examples

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

The first column, read bottom to top (7, 4, 1), becomes the new first row. The second column, read bottom to top (8, 5, 2), becomes the new second row, and so on.

Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]

Input: matrix = [[5]]
Output: [[5]]

A single cell has nothing to rotate around.

Constraints

• n == matrix.length == matrix[i].length

• 1 <= n <= 20

• -1000 <= matrix[i][j] <= 1000

Approach

The easiest way to think about this is to figure out, for every cell, exactly where it lands after the rotation, and place it there directly. Building a brand new grid for that is straightforward, but it costs extra memory equal to the whole grid.

To do it in place with no extra grid, break the rotation into two simpler, well-known steps: first transpose the matrix (flip it across its main diagonal, so matrix[r][c] and matrix[c][r] swap places). Then reverse every row. Doing both, in that order, produces exactly the same result as a single 90-degree clockwise rotation, using no extra grid at all.

Solutions

Brute Force - Build a New Rotated Grid

For a 90-degree clockwise rotation, the cell at row r, column c in the original grid ends up at row c, column (n - 1 - r) in the rotated grid. Build a fresh grid by placing every cell directly into that final position, then copy the result back over the original.

function rotate(matrix) {
  const n = matrix.length;
  const rotated = Array.from({ length: n }, () => new Array(n).fill(0));

  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      rotated[c][n - 1 - r] = matrix[r][c];
    }
  }

  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      matrix[r][c] = rotated[r][c];
    }
  }
}

Time: O(n²) · Space: O(n²)

Optimal - Transpose, Then Reverse Rows

First transpose the grid in place: swap matrix[r][c] with matrix[c][r] for every pair above the main diagonal, which flips the grid across that diagonal. Then reverse each row. Together, these two in-place steps produce exactly a 90-degree clockwise rotation, with no extra grid needed.

function rotate(matrix) {
  const n = matrix.length;

  // Transpose: flip across the main diagonal
  for (let r = 0; r < n; r++) {
    for (let c = r + 1; c < n; c++) {
      [matrix[r][c], matrix[c][r]] = [matrix[c][r], matrix[r][c]];
    }
  }

  // Reverse each row
  for (let r = 0; r < n; r++) {
    matrix[r].reverse();
  }
}

Time: O(n²) · Space: O(1) extra space