#48 Rotate Image - Solution

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

Constraints:

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

Approach	Time Complexity	Space Complexity
Transpose + Reverse Rows	O(n²)	O(1)
Layer-by-Layer Rotation	O(n²)	O(1)

Solutions (12)

Transpose and Reverse

This approach utilizes two main operations. First, we transpose the matrix, which means flipping it over its diagonal. In other words, swap matrix[i][j] with matrix[j][i]. After transposing the matrix, we reverse each row. This combination results in a 90-degree clockwise rotation.

Time Complexity: O(n^2) - Because we loop through each element once.
Space Complexity: O(1) - No extra space is used, operations are in-place.

C C++Java Python C#JavaScript

1function rotate(matrix) {
2    const n = matrix.length;
3    for (let i = 0; i < n; i++) {
4        for (let j = i; j < n; j++) {
5            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
6        }
7    }
8    for (let i = 0; i < n; i++) {
9        matrix[i].reverse();
10    }
11}
12
13const matrix = [
14    [1, 2, 3],
15    [4, 5, 6],
16    [7, 8, 9]
17];
18rotate(matrix);
19console.log(matrix);

Explanation

Utilizes destructuring assignment for transposing elements and uses the Array.reverse function to flip the sequences of each row.

Layer by Layer Rotation

This approach rotates the matrix layer by layer or ring by ring. Start from the outer layer and move to the inner layer, rotating elements by moving them in groups of four. This involves swapping the elements in four-step rotations.

Time Complexity: O(n^2) - Each individual element is moved once.
Space Complexity: O(1) - Done entirely in place, without additional memory.

C C++Java Python C#JavaScript

1using System;

public class Solution {
    public void Rotate(int[][] matrix) {
        int n = matrix.Length;
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer;
            int last = n - 1 - layer;
            for (int i = first; i < last; i++) {
                int offset = i - first;
                int top = matrix[first][i];
                matrix[first][i] = matrix[last - offset][first];
                matrix[last - offset][first] = matrix[last][last - offset];
                matrix[last][last - offset] = matrix[i][last];
                matrix[i][last] = top;
            }
        }
    }

    public static void Main(string[] args) {
        int[][] matrix = new int[3][] {
            new int[] {1, 2, 3},
            new int[] {4, 5, 6},
            new int[] {7, 8, 9}
        };
        Solution sol = new Solution();
        sol.Rotate(matrix);
        foreach (var row in matrix) {
            Console.WriteLine(string.Join(", ", row));
        }
    }
}