0048.Rotate Image

• Link: 48. Rotate Image - Medium
• Track: NeetCode150

Question

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

Restate the problem

• Given a matrix
• In place rotate 90 degree

Edge Case

• size = n x n

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Transpost + Reverse	$O(n^2)$	$O(1)$

Method 1

Key idea: old position: (i, j) → new (j, n - 1 - i)
Step1: swap (j, i) Step2: Reverse row (j, n - 1 - i)

Approach

• Transpose (i, j) → (j, i)
  • Skip the diagonal
  • Only swap upper triangle
  • Diagonal i==j stays the same
• Reverse each row

Complexity

• Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$

Code

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
 
        rows = len(matrix)
        cols = len(matrix[0])
        
        for row in range(rows):
            for col in range(row +1, cols):
                matrix[row][col], matrix[col][row] = matrix[col][row], matrix[row][col]
        
        for row in range(rows):
            matrix[row].reverse()

Dry run

[[1,2,3],       [[1,4,7],      [[7,4,1],
 [4,5,6],   ->   [2,5,8],  ->   [8,5,2],
 [7,8,9]].       [3,6,9]]       [9,6,3]]

---

Common Mistake

• Transpose loops written incorrectly