48. Rotate Image

Rotate Image

Problem Description

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) Brute Force

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    let n = matrix.length;
    for(let x=0; x<Math.ceil(n/2); x++){
		for(let y=x; y<n-x-1; y++){
			let temp = matrix[x][y];
			matrix[x][y] = matrix[n-1-y][x];
			matrix[n-1-y][x] = matrix[n-1-x][n-1-y];
			matrix[n-1-x][n-1-y] = matrix[y][n-1-x];
			matrix[y][n-1-x] = temp;
		}
	}
	return matrix;
};

Approach) Transpose and Reverse

you can get an idea from observation of the index which is swapped.
rotated matrix

20	10	00
21	11	01
22	12	02

• Elements in the first column are from the first row.
• Each sequence of the index in the rows seems reversed like [2x, 1x, 0x]

Algorithm

original matrix

00	01	02
10	11	12
20	21	22

transpose matrix

00	10	20
01	11	21
02	12	22

and then reversed the matrix

20	10	00
21	11	01
22	12	02

/**
 * @param {number[][]} matrix
 * @return {void}.
 */
const rotate = (matrix) => {
    for (let n = 0; n < matrix.length; n++) {
        for (let m = 0; m < matrix.length; m++) {
            if (n === m) break;
            [matrix[n][m], matrix[m][n]] = [matrix[m][n], matrix[n][m]];
        }
    }
    for (let n = 0; n < matrix.length; n++) {
        matrix[n] = matrix[n].reverse();
    }
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 48. Rotate Image

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!