Wednesday, September 16, 2015

Migrating to new domain

Dear Users,

Thanks for your patronage.
I am migrating this blog to my new domain www.letuscode.in
So Problem solving with programming is now "Letuscode.in" .
I will post the latest updates on this new blog from now on. 

I am also planning to migrate all the posts from my old blog to this new blog.
All the posts from this blog are migrated to the new blog.

Monday, August 24, 2015

How to check if sequence is a sub sequence of another

Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.

For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]

The algorithm here is simple. 
  • Let us assume two indices i, j point to the beginning of sub-sequence and sequence respectively.
  • Do the following until we reach the end of any sequence.
  • If both the elements are same, increment both indices.
  • Otherwise increment j only.
At the end of this iteration, if we have seen all the elements of sub-sequence in the given sequence, we are done! otherwise we have not found!

Here is the code in C++ which implements the above approach. This runs in O(n) time and O(1) space. For Python code click here. For Java code click here.


Thursday, August 20, 2015

Finding the pivot element

Given an array of numbers ( minimum length 3), find an index such that all the elements to the left of it are less than or equal, and all the elements to the right of it are greater than it.

For example in the array [1, 2, 3], the pivot element is 2, as all the elements to the left of it are less than 2, and all the elements to the right of it are greater than 2.

The array [6, 9, 1, 2, 4] does not contain any pivot element.

Simple brute force solution:

For each element, check if all the left elements are smaller, and all the right elements are bigger. If there exists any such element we return it's index, otherwise we return -1.
But this solution takes O(n2) time.

Is there any better approach? Can we do it in O(n) time probably using extra space?

Yes, it can be done using two extra arrays.
  • One array stores the maximum element seen so far from the left.
  • Second array stores minimum element seen so far from the right
For example for the array [6, 9, 1, 2, 4]
Prefix maximum: [6, 9, 9, 9, 9]
Suffix minimum: [1, 1, 1, 2, 4] 

We first calculate the above two arrays. In the next iteration, For each element in the array, we check if the maximum element in the left is lesser, and the minimum element in the right is greater than it. If this condition is satisfied we are done. Since checking for maximum element in the left and minimum element in the right takes constant time (O(1)), the overall time complexity of this solution is O(n) and space complexity is O(1).

Below is the C++ implementation of the above. 

Wednesday, August 12, 2015

Minimum number of squares formed from a rectangle

Given a rectangle of some length and width, How do you divide them into minimum number of equal sized squares? This is a problem from Codechef.

For example give a rectangle of size 2 x 4, we can make them into two squares of 2 x 2.
Similarly a rectangle of size 3 x 7, can only be divided into 21 squares each of size 1 x 1.

So what is the logic behind this?
The length and width should be divided in same equal parts, and that part should as greater as possible. So we have to find the GCD(Greatest Common Divisor) of the length and width of the rectangle. Then the minimum number of squares can be calculated by
l/g * w/g. where l = length, w = width, g = GCD(l,w)

Here is the C++ code which implements this.

Monday, August 10, 2015

Ambiguous permutations

Given a permutation of numbers from 1 to N, We can represent it in two ways.

For example, let us consider a permutation from 1 to 5
P = [2 4 1 5 3]
This representation directly indicates the position of each number. i.e 2 is first, 4 is second and so on.

Alternatively, this can also be represented in inverse permutation form.
A = [3 1 5 2 4]
Assuming 1-based index, each number at the index 'i' indicates that the number 'i' is positioned at A[i] in the actual permutation. So this means that 1 appears at index 3, 2 appears at index 1, and so on.

There are some cases when the actual permutation and the inverse permutation are same. We call it as an ambiguous permutation. Now the problem is how do we check if the give permutation is an ambiguous permutation?

The solution is simple. We have to create an inverse permutation in another array, and check if it is same as the original permutation. Calculating the inverse permutation is discussed in my previous post.

Following is the C++ code. It runs in O(n) time and O(n) space.


Friday, August 7, 2015

Duplicate elements in array at given distance

Given an array of numbers A, which might contain duplicate elements, 

How do we find if there are two elements A[i], A[j] such that i, j are distinct and the difference between them is at most k?

Look at the following examples.
1. A = [9, 5, 6, 9, 3, 0, 1], K =3
The answer is "Yes" because 9 is present at index 0, and 3

2. A = [10, 0, 10, 20, 30], K = 1
The answer is "No" because there are no duplicate elements at a distance less than or equal to 1

A simple and straight forward algorithm is to have two loops, the outer loop fixing one element, and the inner loop checks if that element exists within a distance of K. This algorithm runs in O(n2) in worst case.

Let us look at an efficient algorithm using the map data structure. The map stores the element as the key and it's most recent index as it's value. Here are the steps.
  • For each element in the array
    • Store the element and it's index in the map if does not exist already.
    • If already exists, 
      • Check if the difference between the recent index and current index is less than K. 
      • If so return true.
      • Otherwise update the map with recent index
This algorithm runs in O(n log n) time, and take O(n) extra space for the map. Here is the C++ code given below. For the Python implementation checkout this link. For Java implementation check this link.

Monday, August 3, 2015

Mirror image of a binary tree

Given a binary tree, how to convert it to it's mirror image?
For example consider the following binary tree and it's mirror image.
Here simply, the left and right sub trees of each node are inverted. So we have to simply invert the given binary tree. It is a simple implementation problem. Using recursion we can solve it by following the below steps
  1. If root is NULL, simply return
  2. Invert the left sub tree
  3. Invert the right sub tree
  4. Swap left and right sub trees.
Here is the C++ code which implements the above algorithm. It runs in O(n) time.