Difficulty: Medium Link: April Leetcode Challenge: Day 25
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.
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]]
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]]
Input: matrix = [] Output: []
Input: matrix = [[1,2],[3,4]] Output: [[3,1],[4,2]]
matrix.length == n
matrix[i].length == n
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
The problem is simple if we can understand the trick which will lead us to the solution. This problem can be solved in various ways, but we will be looking using the matrix properties and operations. If we look carefully, the every column of the matrix in input gets converted into a column in the output (But in reverse). Now what operation does it closely resembles to?
To find the transpose of the matrix, we simply need to traverse in using two loops and swap the element at (i , j) to (j, i). This is a simple operation and after that we can see that every column value maps to a row but elements need to be reversed. We can now loop through every row and reverse the matrix.
Be careful to loop till only half columns while reversing otherwise elements would get reversed twice and the matrix remains the same.
We are iterating every element in the 2D matrix hence complexity would be in the order of matrix elements. Same is for the transpose and reversing row operations. Since solution was required to be in-place it is a constant space operation.
Time = O(N2)
Space = O(1)