Topic: Matrix Rotation


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!

Illustration to show movement of swaps.

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
                

Can you find this code’s complexity? Comment below.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.