48. Rotate Image

Intuition

To rotate the matrix 90 degrees clockwise, we can break down the problem into two simpler steps:

1. Reverse the rows of the matrix (vertical flip).
2. Transpose the matrix (convert rows to columns).

Approach

1. Vertical Flip: - Initialize top to the first row (index 0) and bottom to the last row (index edgeLength - 1). - Swap the elements of the top row with the bottom row for each column. - Move top down and bottom up until they meet.
2. Transpose the Matrix: - Iterate over each element above the main diagonal. - Swap the element at position (row, col) with the element at position (col, row).

Complexity

Time Complexity:

O(n^2)

• We iterate over all elements in the matrix twice: once for the vertical flip and once for the transpose. Therefore, the time complexity is O(n^2).

Space Complexity:

O(1)

• We perform the operations in-place without using any extra space apart from a few temporary variables for swapping. Therefore, the space complexity is O(1).

Code

C++

class Solution {
public:
    void rotate(vector>& matrix) {
        int edgeLength = matrix.size();
        int top = 0;
        int bottom = edgeLength - 1;
        while (top < bottom) {
            for (int col = 0; col < edgeLength; ++col) {
                int temp = matrix[top][col];
                matrix[top][col] = matrix[bottom][col];
                matrix[bottom][col] = temp;
            }
            top++;
            bottom--;
        }
        for (int row = 0; row < edgeLength; ++row) {
            for (int col = row + 1; col < edgeLength; ++col) {
                int temp = matrix[row][col];
                matrix[row][col] = matrix[col][row];
                matrix[col][row] = temp;
            }
        }
    }
};

Python

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        edgeLength = len(matrix)
        top = 0
        bottom = edgeLength - 1
        while top < bottom:
            for col in range(edgeLength):
                matrix[top][col], matrix[bottom][col] = matrix[bottom][col], matrix[top][col]
            top += 1
            bottom -= 1
        for row in range(edgeLength):
            for col in range(row + 1, edgeLength):
                matrix[row][col], matrix[col][row] = matrix[col][row], matrix[row][col]

Java

class Solution {
    public void rotate(int[][] matrix) {
        int edgeLength = matrix.length;
        int top = 0;
        int bottom = edgeLength - 1;
        while (top < bottom) {
            for (int col = 0; col < edgeLength; col++) {
                int temp = matrix[top][col];
                matrix[top][col] = matrix[bottom][col];
                matrix[bottom][col] = temp;}
            top++;
            bottom--;}
        for (int row = 0; row < edgeLength; row++) {
            for (int col = row + 1; col < edgeLength; col++) {
                int temp = matrix[row][col];
                matrix[row][col] = matrix[col][row];
                matrix[col][row] = temp;
            }
        }
    }
}

JavaScript

var rotate = function(matrix) {
    const edgeLength = matrix.length;
    let top = 0;
    let bottom = edgeLength - 1;
    while (top < bottom) {
        for (let col = 0; col < edgeLength; col++) {
            let temp = matrix[top][col];
            matrix[top][col] = matrix[bottom][col];
            matrix[bottom][col] = temp; }
        top++;
        bottom--;}
    for (let row = 0; row < edgeLength; row++) {
        for (let col = row + 1; col < edgeLength; col++) {
            let temp = matrix[row][col];
            matrix[row][col] = matrix[col][row];
            matrix[col][row] = temp;
        }
    }    
};