Skip to content

48. Rotate Image 👍

Approach 1: Reverse

  • Time: $O(n^2)$
  • Space: $O(1)$
1
2
3
4
5
6
7
8
9
class Solution {
 public:
  void rotate(vector<vector<int>>& matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i)
      for (int j = i + 1; j < matrix.size(); ++j)
        swap(matrix[i][j], matrix[j][i]);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public void rotate(int[][] matrix) {
    for (int i = 0, j = matrix.length - 1; i < j; ++i, --j) {
      int[] temp = matrix[i];
      matrix[i] = matrix[j];
      matrix[j] = temp;
    }

    for (int i = 0; i < matrix.length; ++i)
      for (int j = i + 1; j < matrix.length; ++j) {
        final int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
      }
  }
}

1
2
3
4
5
6
7
class Solution:
  def rotate(self, matrix: List[List[int]]) -> None:
    matrix.reverse()

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

Approach 2: Indexing

  • Time: $O(n^2)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  void rotate(vector<vector<int>>& matrix) {
    for (int min = 0; min < matrix.size() / 2; ++min) {
      const int max = matrix.size() - min - 1;
      for (int i = min; i < max; ++i) {
        const int offset = i - min;
        const int top = matrix[min][i];
        matrix[min][i] = matrix[max - offset][min];
        matrix[max - offset][min] = matrix[max][max - offset];
        matrix[max][max - offset] = matrix[i][max];
        matrix[i][max] = top;
      }
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public void rotate(int[][] matrix) {
    for (int min = 0; min < matrix.length / 2; ++min) {
      final int max = matrix.length - min - 1;
      for (int i = min; i < max; ++i) {
        final int offset = i - min;
        final int top = matrix[min][i];
        matrix[min][i] = matrix[max - offset][min];
        matrix[max - offset][min] = matrix[max][max - offset];
        matrix[max][max - offset] = matrix[i][max];
        matrix[i][max] = top;
      }
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def rotate(self, matrix: List[List[int]]) -> None:
    for min in range(len(matrix) // 2):
      max = len(matrix) - min - 1
      for i in range(min, max):
        offset = i - min
        top = matrix[min][i]
        matrix[min][i] = matrix[max - offset][min]
        matrix[max - offset][min] = matrix[max][max - offset]
        matrix[max][max - offset] = matrix[i][max]
        matrix[i][max] = top