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

Algorithms Basics: Topic – Recursion


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.

Recursive functions:

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.

def fib(n):
	if(n>0):
		if(n==1):
			return 0
		if(n==2):
			return 1
		else:
			return fib(n-1) + fib(n-2)

Fork the code yourself here!

Properties of recursive functions:

  • Recursive functions have two cases:
    • A base case: where the function terminates.
    • A recursive case: where the function calls itself.
  • Every recursive function must terminate at base case. If not defined, the function goes into infinite loop and hence result in stack overflow.
  • Recursive functions store the function information in stack memory.
  • Every algorithm modeled using recursive function can also be modeled using iterative functions by using stack data structures.
  • Iterative solutions are more efficient than recursive functions due to the overhead of extra function calls and stack memory usage.
  • Recursive functions are used since it is easy to visualize the algorithm using recursive approach.
  • For some problems there are no obvious iterative approach algorithms, and hence recursive functions are preferred.

Examples of recursive algorithms:

  1. Fibonacci Series. Try yourself here!
  2. Factorial of a number. Try yourself here!
  3. Merge Sort.
  4. Quick Sort.