Friday, March 21, 2014

Generating a pascal triangle

In this post, we will write a program to generate a pascal triangle of given height.

For example, Pascal triangle of height 5 is shown below

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

The idea behind Pascal triangle is that each element in a row is the sum of left and right elements in the previous row. If the previous row does not contain left/right, they are considered as 0. The same idea is used to write simple program like the following.


Thursday, March 20, 2014

Merging two sorted arrays

Given two sorted arrays A, B of lengths m, n respectively. How to merge them into a single sorted array?. Let us assume that A has sufficient space (m+n) for result array.

For example let A = [1, 3, 5, 7, 9], and B = [2, 4, 6, 8, 10]. The function should return A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] as a result.

Since the array A has sufficient space for the merged array, we can start from the end of the array A and start filling the result elements.

We compare the elements at i and j indices. We move the bigger element to the end pointed by res and decrement the corresponding index. We do this until we reach the beginning of any array. Finally we check if there any left over elements in the second array. If there are, we have to move them to the first array.


Wednesday, March 19, 2014

Removing all instances of a number in an array

Given an array of arbitrary numbers and a given value, how do we write a program to delete all instances of the given value?

For example, if the input array is [23, 9, 18, 9, 6, 47, 3, 6] and the element to be deleted is 9. The result array should be [23, 18, 6, 47, 3, 6]. Result array size is 6. We don't care about the elements beyond this size.

The restriction is to modify the input array itself (should not use extra memory - constant extra space) and return the new length of the result array.

This problem can be solved as follows.
 
We maintain two indices; one to track the elements of resultant array (result index), and another to iterate through all the elements. While iterating through each element using second index, if we see an element which is not equal to the target element, we can copy it to the same array from the beginning, and increment the result index.

This algorithm runs in O(n) time and O(1) space complexity.

Here is the simple implementation in C++.

Monday, March 17, 2014

Finding an element in a circularly sorted array

Given a circularly sorted array, how to search for an element efficiently?

For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3.

Since the array is sorted but rotated, we can expect it to be solved using the binary search technique.

We can design an algorithm like this. We first check if the middle element equals the target element. If so, we return the mid.

Otherwise we check to see if the left half is sorted or right half is sorted. In any case only one portion will be sorted. We have to narrow down our search based on the range of elements which the target belongs to .

           if( arr[low] <= arr[mid]) //left half is sorted
        {
            //If target lies in first half

            if( s >= arr[low] && s < arr[mid] )
                high = mid - 1;
            else
                low = mid + 1; // narrow down to right half
        }
        else // Right half is sorted
        {
            if( s > arr[mid] && s <= arr[high] )
                low = mid + 1;
            else
                high = mid - 1;
        }


Here is the iterative implementation of the above algorithm. This algorithm runs in O( log n ) time complexity.

 

Saturday, March 15, 2014

How many times a sorted array is rotated?

Given a circularly sorted array of unique elements, how do we efficiently find the number of rotations?

For example the array [4, 5, 1, 2, 3] is (right) rotated twice.

Before proceeding to find a solution, let's note some observations.

To find the number of rotations, we have to find the smallest element in the array. If we find the index of the smallest element in the array, that will indicate the number of rotations.

In the above example, the smallest number is 1 which is located at index '2'. We can easily verify that the array is rotated twice.

A simple approach could be to use a linear search to find the least number and return it's index. This approach will obviously take O(n) time. Can we perform better than that?

Yes, it can be done by utilizing the sorted property of the array. Here is how we can do this.

Just like Binary search, we can use divide and conquer approach. We write a recursive function which will take the array, lower and upper bound as its parameters.


We first check whether the array is sorted from the beginning (not rotated). This can be done by checking if array[low] <= array[high]. If it is not rotated, we can simply return the index low.

Next we check if the middle element is the smallest element by comparing it with the previous and next elements.

if( array[mid] < array[prev] && array[mid] < array[next] )

If this condition is satisfied, then we return mid. One caution while calculating the next and previous indices is to consider the array boundaries. We have to assume that the array is circular.

      //if mid is at 0, consider last element as previous
     int prev = (mid - 1 + len) % len;
   //if mid is the last element, consider next element as the first

     int next = (mid + 1) % len;

Next, we check which portion is already sorted. If the left portion is properly sorted (without rotations), we search in the right half. Otherwise we search in the left half.

     if( arr[low] <= arr[mid] )
        return findRotations(arr, mid+1, high);
    else
        return findRotations(arr, low, mid-1);

Here is the C++ code which implements the above algorithm.

Even more simplified version of the algorithm is given below. 

int findRotationCount(const vector<int>& arr)
{
 int low = 0, high = arr.size() - 1;
 
 while( arr[low] > arr[high] )
 {
  int mid = low + (high - low)/2;
  if( arr[mid] > arr[high] )
   low = mid + 1;
  else
   high = mid;
 }
 return low;
}
int findRotateCount(const vector<int>& arr, int low, int high)
{
 if( arr[low] > arr[high] )
 {
  int mid = low + (high-low)/2;
  if( arr[mid] > arr[high] )
   return findRotateCount( arr, mid+1, high);
  else
   return findRotateCount( arr, low, mid);
 }
 else
  return low;
}