Rotate Image

Share

Given an n x n 2D matrix, rotate it 90 degrees clockwise in-place.

Example 1
Input: [[1,2,3],[4,5,6],[7,8,9]] → Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2
Input: [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] → Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Solution Approach

Two-step process: (1) Transpose the matrix (swap matrix[i][j] with matrix[j][i]); (2) Reverse each row.

  • Transpose: for i from 0 to n-1: for j from i+1 to n-1: swap matrix[i][j] and matrix[j][i].
  • Reverse each row: for each row, use two pointers to reverse.
Java
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // Transpose
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++) { int t=matrix[i][j]; matrix[i][j]=matrix[j][i]; matrix[j][i]=t; }
        // Reverse each row
        for (int[] row : matrix) {
            int lo=0, hi=row.length-1;
            while (lo<hi) { int t=row[lo]; row[lo]=row[hi]; row[hi]=t; lo++; hi--; }
        }
    }
}
  • Time Complexity: O(N^2)
  • Space Complexity: O(1)