rotate-image.ts

/**
 * 48. Rotate Image  (Medium)
 * Link: https://leetcode.com/problems/rotate-image/
 *
 * Rotate an n x n matrix 90 degrees clockwise, in place.
 *
 * Example:
 *   Input:  [[1,2,3],[4,5,6],[7,8,9]]
 *   Output: [[7,4,1],[8,5,2],[9,6,3]]
 *
 * Approach:
 *   A 90° clockwise rotation equals transpose (swap across the main diagonal)
 *   followed by reversing each row. Both steps are in place, so no extra matrix
 *   is allocated.
 *
 * Time:  O(n^2)
 * Space: O(1)
 */
export function rotate(matrix: number[][]): void {
  const n = matrix.length;

  // transpose
  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();
  }
}