Rotate Image [Matrix]

48.Rotate Image

Array

Matrix

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.

Example:

Input:

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

→

Output:

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

The matrix is rotated clockwise by 90 degrees.

Algorithm:

1. Clockwise Rotation (90° right):
   • Step 1: Reverse rows from up to down
   • Step 2: Transpose the matrix
2. Counter-clockwise Rotation (90° left):
   • Step 1: Reverse each row (left to right)
   • Step 2: Transpose the matrix

Complexity:

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

Java Solution:

public void rotate(int[][] matrix) {
    int n = matrix.length;

    // Step 1: Reverse the matrix up to down
    // For clockwise: reverse rows [1,2,3] [4,5,6] [7,8,9] to [7,8,9] [4,5,6] [1,2,3]
    // For counter-clockwise: reverse each row instead [3,2,1] [6,5,4] [9,8,7]
    for (int i = 0; i < matrix.length/2; i++) {
        int[] temp = matrix[i];
        matrix[i] = matrix[n - i - 1];
        matrix[n - i - 1] = temp;
    }
    
    // Step 2: Transpose the matrix
    // Swap matrix[i][j] with matrix[j][i] for all i < j
    // Changes [7,8,9] [4,5,6] [1,2,3] to [7,4,1] [8,5,2] [9,6,3]
    for (int i = 0; i < matrix.length; i++) {
        for (int j = i + 1; j < matrix[0].length; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

// For counter-clockwise rotation (bonus)
public void rotateCounterClockwise(int[][] matrix) {
    int n = matrix.length;
    
    // Step 1: Reverse each row left to right
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n/2; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][n - 1 - j];
            matrix[i][n - 1 - j] = temp;
        }
    }
    
    // Step 2: Same transpose operation
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

Python Solution:

def rotate(self, matrix: List[List[int]]) -> None:
    n = len(matrix)
    
    # Step 1: Reverse up to down
    matrix.reverse()
    
    # Step 2: 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]

# For counter-clockwise rotation
def rotateCounterClockwise(self, matrix: List[List[int]]) -> None:
    n = len(matrix)
    
    # Step 1: Reverse each row
    for row in matrix:
        row.reverse()
    
    # Step 2: 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]

C++ Solution:

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    
    // Step 1: Reverse up to down
    reverse(matrix.begin(), matrix.end());
    
    // Step 2: Transpose
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
}

// For counter-clockwise rotation
void rotateCounterClockwise(vector<vector<int>>& matrix) {
    int n = matrix.size();
    
    // Step 1: Reverse each row
    for (auto& row : matrix) {
        reverse(row.begin(), row.end());
    }
    
    // Step 2: Transpose
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
}