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 mn = 0; mn < matrix.size() / 2; ++mn) {
      const int mx = matrix.size() - mn - 1;
      for (int i = mn; i < mx; ++i) {
        const int offset = i - mn;
        const int top = matrix[mn][i];
        matrix[mn][i] = matrix[mx - offset][mn];
        matrix[mx - offset][mn] = matrix[mx][mx - offset];
        matrix[mx][mx - offset] = matrix[i][mx];
        matrix[i][mx] = 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 mn = 0; mn < matrix.length / 2; ++mn) {
      final int mx = matrix.length - mn - 1;
      for (int i = mn; i < mx; ++i) {
        final int offset = i - mn;
        final int top = matrix[mn][i];
        matrix[mn][i] = matrix[mx - offset][mn];
        matrix[mx - offset][mn] = matrix[mx][mx - offset];
        matrix[mx][mx - offset] = matrix[i][mx];
        matrix[i][mx] = top;
      }
    }
  }
}

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