Rotate Image - Leetcode Solution

Problem Statement:

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

You have to modify the input matrix in-place. Do not allocate another 2D matrix and do not return anything from your function.

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 = [[1]] Output: [[1]]

Approach:

In this problem, we need to rotate an image by 90 degrees. We can do this by swapping the elements in clockwise direction. We can swap the elements in the matrix in a nested loop.

We iterate over the first half of the matrix (i < n/2) and for each element, we swap it with the corresponding element in the clockwise direction. We do the swapping in four steps.

Let's take an example of a 3 x 3 matrix:

Initial Matrix:

1 2 3 4 5 6 7 8 9

Step 1: Swap the elements as shown below:

7 2 1 4 5 6 9 8 3

Step 2: Swap the elements as shown below:

7 4 1 2 5 8 9 6 3

Step 3: Swap the elements as shown below:

7 4 1 8 5 2 9 6 3

This is the final rotated matrix.

Implementation:

Let's take the example of a 3 x 3 matrix to explain the approach.

We have an input matrix of:

1 2 3 4 5 6 7 8 9

We need to swap the elements of this matrix to get the final matrix:

7 4 1 8 5 2 9 6 3

Step 1: Swap the elements

To do this, we need to use a nested loop to iterate over the first half of the matrix. We only need to iterate over the first half of the matrix because we are swapping the elements in place.

We can swap the elements using a temporary variable.

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;
	}
}

Step 2: Print the rotated matrix

After swapping the elements, we can print the rotated matrix as follows:

for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
    	cout << matrix[i][j] << " ";
	}
	cout << endl;
}

This will print the following matrix:

7 4 1 8 5 2 9 6 3

The full implementation code for this problem is given below:

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; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << matrix[i][j] << " "; } cout << endl; } }

This implementation has a time complexity of O(n^2) because we need to swap n^2/2 elements. It also has a space complexity of O(1) because we are swapping the elements in place.

1