In this section, I will be discussing a simple yet not so intuitive approach to solving matrix rotation problem. So the problem statement is to rotate a NxN matrix clock wise 90 degrees in an efficient way. I can think of it as Rubic’s Cube one side rotation.
Now what all changes when a matrix is rotated 90 degrees:
- row 1 becomes last column,
- row 2 becomes last second column,
- row last becomes first column
Now I approach this problem in the following way…
- Take one outer boundary at a time. Just the boundary.
- Top right is at 0,0 index
- Top left is at 0, len(A)-1 index
- Bottom right is at len(A)-1, len(A)-1 index
- Bottom left is at len(A)-1, 0 index
Now simply swap these four cells clock wise. top-left with top-right, top-right with bottom-right, bottom-right with bottom-left, and finally bottom left with top-left. Now just move one step ahead in clockwise direction.
When you are done with outer boundary movement, take a step into one layer inner circle, and perform above swaps the same way!
Below is the python code for same.
class Matrix_Rotation: # @param A : list of list of integers # @return the same list modified def rotate90Clockwise(self, A): for steps in range((len(A)/2)): for move_ahead in range(len(A)-1-steps*2): temp = A[len(A)-1-move_ahead-steps][steps] A[len(A)-1-move_ahead-steps][steps] = A[len(A)-1-steps][len(A)-1-move_ahead-steps] A[len(A)-1-steps][len(A)-1-move_ahead-steps] = A[steps+move_ahead][len(A)-steps-1] A[steps+move_ahead][len(A)-steps-1] = A[steps][steps+move_ahead] A[steps][steps+move_ahead] = temp return A