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.
# @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
Can you find this code’s complexity? Comment below.
Recursive functions are well known in the domain on algorithms. They are widely used due to their simplicity of code. Here we describe the topic of recursion.
Any function that calls itself is called a recursive function!
Yep! It’s just that simple. Let me explain with an example. Below is the code for fibonacci series. Note how fib() takes an input of (n) and returns the n-th term of the series. This function calls itself when n>2. This is a typical example of recursive functions.