48. Rotate Image

Description

Question

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.

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]]

Approach

Now rotating each element 90 degrees one by one is very inefficient. So we can break this into two deterministic problems.

1. Transpose the matrix: Converting rows into columns. j=i+1
2. Reverse each row: Mirrors the matrix resulting in 90 degree rotation. j with n - j - 1.

Code

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

    // Transpose here
    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]
        }
    }

    // Reversing Rows
    for i:=0;i<n;i++{
        for j:=0;j<n/2;j++{
            matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]
        }
    }
}

Complexity Analysis

• Time complexity: (O(n^2)) — We are using nested loops, every element is visited a constant number of times.
• Space complexity: (O(1)) — in-place modification, no extra memory used. No complex index mapping.