LeetCode Problem

Problem Description

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

Examples

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

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

Constraints

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Follow-up

Approach to Solve

Rotate the matrix in place by performing a four-way swap for each element in the top-left quadrant.

Code Implementation

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n // 2):
            for j in range(i, n - i - 1):
                temp = matrix[i][j]
                matrix[i][j] = matrix[n - j - 1][i]
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
                matrix[j][n - i - 1] = temp

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - i - 1; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - i - 1; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

Explanation

This solution rotates the matrix in place by performing a four-way swap for each element in the top-left quadrant. Here's a detailed explanation of the algorithm:

Get the size of the matrix n.
Iterate over each element in the top-left quadrant of the matrix (i.e., from i = 0 to n // 2 and j = i to n - i - 1).
For each element at position (i, j), perform a four-way swap to rotate it to its new position:
- temp = matrix[i][j]
- matrix[i][j] = matrix[n - j - 1][i]
- matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
- matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
- matrix[j][n - i - 1] = temp
The four-way swap ensures that each element is rotated to its correct position in the matrix.
The process is repeated for all elements in the top-left quadrant, effectively rotating the entire matrix by 90 degrees clockwise.

The time complexity is O(n^2) because we visit each cell in the matrix once. The space complexity is O(1) as we perform the rotation in place without using any additional data structures that grow with the input size.

Complexity

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

LeetSolved

Rotate Image