48. Rotate Image

Problem Description

You're given a square matrix, which is a 2D array, and your task is to rotate this image by 90 degrees clockwise. To clarify, rotating an image by 90 degrees clockwise means that the image is turned in such a way that if you start from the top left corner of the original image, it would become the top right corner of the rotated image. However, the challenge is to perform this rotation in-place, that is, without using any extra space for another array. You'll need to transform the matrix within the given data structure itself.

Intuition

To rotate the matrix by 90 degrees clockwise, you can think of a two-step process. First, imagine if you flip the image upside down, which can be visualized as folding the bottom row up to where the top row is, and vice versa. This can be done by swapping the elements in the first row with the corresponding elements in the last row, then the second row with the second-to-last row, and so on until you reach the middle of the matrix.

Once the matrix is flipped upside down, the next step is to flip it along its main diagonal. The main diagonal of a matrix is a line of entries starting from the top-left corner to the bottom-right corner. Flipping a matrix along the main diagonal means that for each element matrix[i][j], you swap it with the element matrix[j][i].

By following these two steps - flipping the matrix upside down and then swapping elements along the main diagonal - each element moves to its correct position as it would be after a 90-degree clockwise rotation.

Learn more about Math patterns.

Solution Approach

The solution provided is a two-step process that involves:

Flipping the matrix upside down.
Then, flipping the matrix along its main diagonal.

For the first step, the code iterates through the first half of the rows (hence the range(n >> 1) which is a bitwise shift operation equivalent to range(n // 2)) and swaps all elements in row i with the corresponding elements in row n-i-1. The swapping is done column by column for each row (for j in range(n):). This effectively turns the matrix upside down without using any additional space.

Once the matrix is flipped upside down, we proceed with the second step, which involves swapping elements across the main diagonal. We iterate row by row, and within each row, we only go up to the main diagonal (for j in range(i)) to avoid re-swapping the already swapped elements. At each iteration, we swap the element at position [i][j] with the element at position [j][i]. This flips the matrix along the main diagonal and completes the 90-degree rotation.

The patterns used in this algorithm are in-place replacement to avoid additional memory usage, and careful indexing to walk through the 2D matrix in the required order. The operations of this method are designed to achieve the rotation with only O(1) additional space, by performing swaps directly on the given matrix.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Suppose we have the following 3x3 matrix (a square matrix with 3 rows and 3 columns):

1 2 3
4 5 6
7 8 9

We want to rotate this matrix by 90 degrees clockwise.

Step 1: Flipping the matrix upside down.

We start by flipping the entire matrix upside down, which involves swapping rows first with last, and so on until reaching the middle of the matrix. We swap the 1st row with the 3rd row, and because we have an odd number of rows (3), the middle row (2nd row) stays in place.

After flipping upside down, the matrix will look like this:

7 8 9
4 5 6
1 2 3

We can see that the 1st row has become the last row and the last row has become the 1st row.

Step 2: Flipping the matrix along its main diagonal.

Next, we need to flip the matrix along its main diagonal to achieve the 90-degree rotation. We swap the elements symmetrically across the diagonal. The main diagonal (1 to 9) doesn't change place.

For our example, this means swapping element (2,1) with (1,2), then (3,1) with (1,3), and finally (3,2) with (2,3) — note how we don't swap elements on the main diagonal itself or elements that have already been swapped.

Here's how we perform each swap:

Swap element (2,1) with (1,2) — swaps 4 with 8 which gives us:
```
7 4 9
8 5 6
1 2 3
```
Swap element (3,1) with (1,3) — swaps 1 with 9 which gives us:
```
7 4 1
8 5 6
9 2 3
```
Swap element (3,2) with (2,3) — swaps 2 with 6 which gives us:
```
7 4 1
8 5 2
9 6 3
```

After performing these swaps, the final matrix after a 90-degree clockwise rotation is:

7 4 1
8 5 2
9 6 3

If you visualize turning the original matrix by 90 degrees clockwise, you will see that this final matrix is indeed the original matrix rotated, and just as importantly, the transformation has been performed in place, using no additional storage space.

Solution Implementation

1class Solution:
2    def rotate(self, matrix):
3        # Determine the size of the matrix
4        size = len(matrix)
5
6        # Perform a vertical flip of the matrix
7        for i in range(size >> 1):  # size >> 1 is a faster way to do size // 2
8            for j in range(size):
9                # Swap the top and bottom elements in the column
10                matrix[i][j], matrix[size - i - 1][j] = matrix[size - i - 1][j], matrix[i][j]
11
12        # Perform a diagonal flip of the matrix, which is equivalent
13        # to transposing the matrix
14        for i in range(size):
15            for j in range(i):
16                # Swap the elements across the diagonal
17                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
18

1class Solution {
2    public void rotate(int[][] matrix) {
3        // Obtain the length of the matrix which is a square (same width and height)
4        int n = matrix.length;
5
6        // Step 1: Perform a vertical flip of the matrix
7        // Loop over the first half of the rows (vertically)
8        for (int row = 0; row < (n >> 1); ++row) {
9            // Loop over all columns
10            for (int col = 0; col < n; ++col) {
11                // Swap the element at the current position with the element at the mirrored row
12                // across the horizontal axis
13                int temp = matrix[row][col];
14                matrix[row][col] = matrix[n - row - 1][col];
15                matrix[n - row - 1][col] = temp;
16            }
17        }
18
19        // Step 2: Transpose the matrix by flipping it along its diagonal
20        // Loop over all rows
21        for (int row = 0; row < n; ++row) {
22            // Loop over the columns up to the current row (to avoid re-flipping)
23            for (int col = 0; col < row; ++col) {
24                // Swap the element at (row, col) with the element at (col, row)
25                int temp = matrix[row][col];
26                matrix[row][col] = matrix[col][row];
27                matrix[col][row] = temp;
28            }
29        }
30    }
31}
32

1#include <vector>
2#include <algorithm> // For std::swap
3using std::vector;
4using std::swap;
5
6class Solution {
7public:
8    // Function to rotate the matrix by 90 degrees clockwise.
9    void rotate(vector<vector<int>>& matrix) {
10        int size = matrix.size();
11      
12        // First step: Reverse every row of the matrix.
13        // (Equivalent to a vertical reflection of the matrix)
14        for (int row = 0; row < size / 2; ++row) {
15            for (int col = 0; col < size; ++col) {
16                // swap elements symmetrically along
17                // the middle row of the matrix
18                swap(matrix[row][col], matrix[size - row - 1][col]);
19            }
20        }
21      
22        // Second step: Swap the symmetric elements across the diagonal
23        // (top-left to bottom-right).
24        for (int i = 0; i < size; ++i) {
25            for (int j = 0; j < i; ++j) {
26                // swap elements to achieve 90-degree rotation
27                swap(matrix[i][j], matrix[j][i]);
28            }
29        }
30      
31        // At the end of these two steps, the matrix is rotated 90 degrees clockwise.
32    }
33};
34

1/**
2 * Rotates an N x N matrix by 90 degrees clockwise.
3 * @param matrix The N x N matrix to rotate (will be modified in place).
4 */
5function rotate(matrix: number[][]): void {
6    // First, reverse the rows of the matrix to position elements for the rotation.
7    matrix.reverse();
8
9    // Then, swap the elements along the diagonal.
10    // Only iterate through the first row up to row before the last,
11    // since after that elements would have already been swapped.
12    for (let row = 0; row < matrix.length; ++row) {
13        // Swap elements across the diagonal, hence j starts from row + 1 to prevent swapping elements twice.
14        for (let col = 0; col < row; ++col) {
15            // Temporary variable to hold the current element to be swapped.
16            const temp = matrix[row][col];
17
18            // Swap the element with its transposed position element.
19            matrix[row][col] = matrix[col][row];
20            matrix[col][row] = temp;
21        }
22    }
23}
24

Time and Space Complexity

The time complexity of the given code is O(n^2), where n is the length of the matrix. This is because there are two nested loops that iterate over the elements of the matrix. The first set of nested loops is responsible for the vertical flipping of the matrix (first part of the rotation), and it iterates over half of the matrix rows (hence n/2) for all columns, but since we drop constants when expressing time complexity, it simplifies to O(n^2).

The second part of the rotation is swapping elements across the diagonal, again involving a nested loop, but this time it only processes elements in the upper triangle (excluding the diagonal) of the matrix, which still leads to a total of n*(n-1)/2 swaps. Despite the fact that only roughly half of the matrix elements are being swapped (upper triangle), this still results in a time complexity of O(n^2) because the leading term n^2 dominates as n grows large.

As for the space complexity, the reference answer correctly states it is O(1). The algorithm only uses a constant amount of extra space for variable storage, regardless of the size of the input matrix. The rotation is done in place, therefore no additional space proportional to the input size is required.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don’t know