🟨 Rotate Image (#48)

🔗 Problem Link

• LeetCode - Rotate Image
• NeetCode - Rotate Image

📋 Problem Statement

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

💡 Examples

Example 1

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

Example 2

Input: matrix = [[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]]

🔑 Key Insights & Approach

Core Observation: Transpose matrix then reverse each row (or vice versa for counterclockwise).

Why Transpose + Reverse?

• O(n²) time, O(1) space
• In-place rotation
• Two simple operations

Pattern: "Matrix Manipulation" pattern.

🐍 Solution: Python

Approach: Transpose + Reverse

Time Complexity: O(n²) | Space Complexity: O(1)

from typing import List

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)

        # Transpose
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        # Reverse each row
        for i in range(n):
            matrix[i].reverse()

🔵 Solution: Golang

Approach: Transpose + Reverse

Time Complexity: O(n²) | Space Complexity: O(1)

func rotate(matrix [][]int) {
    n := len(matrix)

    // Transpose
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }

    // Reverse each row
    for i := 0; i < n; i++ {
        for j, k := 0, n-1; j < k; j, k = j+1, k-1 {
            matrix[i][j], matrix[i][k] = matrix[i][k], matrix[i][j]
        }
    }
}

📚 References

• NeetCode - Rotate Image