Maximum single sell profit from stock

Problem
Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit.

OR

Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[].


Example
Input = {5        10         4         6        7}
Output = 5,10 => buy at 5 and sell at 7

Solution

Method 1 - Brute force
Clearly there is an O(n²) solution to the algorithm by trying out all possible (buyDay, sellDay) pairs and taking the best out of all of them. However, is there a better algorithm, perhaps one that runs in O(n) time?

int maxDiff(int arr[], int arr_size)
{     
  int max_diff = arr[1] - arr[0];
  int i, j;
  for(i = 0; i < arr_size; i++)
  {
    for(j = i+1; j < arr_size; j++)
    {        
      if(arr[j] - arr[i] > max_diff)   
         max_diff = arr[j] - arr[i];
    }    
  }          
  return max_diff;
}    

Method 2 - Divide and Conquer
If we have a single day, the best option is to buy on that day and then sell it back on the same day for no profit. Otherwise, split the array into two halves. If we think about what the optimal answer might be, it must be in one of three places:

1. The correct buy/sell pair occurs completely within the first half.
2. The correct buy/sell pair occurs completely within the second half.
3. The correct buy/sell pair occurs across both halves - we buy in the first half, then sell in the second half.

We can get the values for (1) and (2) by recursively invoking our algorithm on the first and second halves. For option (3), the way to make the highest profit would be to buy at the lowest point in the first half and sell in the greatest point in the second half. We can find the minimum and maximum values in the two halves by just doing a simple linear scan over the input and finding the two values. This then gives us an algorithm with the following recurrence:

T(1) <= O(1)
T(n) <= 2T(n / 2) + O(n)

Using the Master Theorem to solve the recurrence, we find that this runs in O(n lg n) time and will use O(lg n) space for the recursive calls. We've just beaten the naive O(n²) solution!

Method 3 - Optimized divide and conquer
But wait! We can do much better than this. Notice that the only reason we have an O(n) term in our recurrence is that we had to scan the entire input trying to find the minimum and maximum values in each half. Since we're already recursively exploring each half, perhaps we can do better by having the recursion also hand back the minimum and maximum values stored in each half! In other words, our recursion hands back three things:

1. The buy and sell times to maximize profit.
2. The minimum value overall in the range.
3. The maximum value overall in the range.

These last two values can be computed recursively using a straightforward recursion that we can run at the same time as the recursion to compute (1):

1. The max and min values of a single-element range are just that element.
2. The max and min values of a multiple element range can be found by splitting the input in half, finding the max and min values of each half, then taking their respective max and min.

If we use this approach, our recurrence relation is now

T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)

Using the Master Theorem here gives us a runtime of O(n) with O(lg n) space, which is even better than our original solution!

Method 4 - Use the difference between adjacent element
First find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. Now this problems turns into finding the maximum sum subarray of this difference array.

int maxDiff(int arr[], int n)
{
    // Create a diff array of size n-1. The array will hold
    //  the difference of adjacent elements
    int diff[n-1];
    for (int i=0; i < n-1; i++)
        diff[i] = arr[i+1] - arr[i];
 
    // Now find the maximum sum subarray in diff array
    int max_diff = diff[0];
    for (int i=1; i<n-1; i++)
    {
        if (diff[i-1] > 0)
            diff[i] += diff[i-1];
        if (max_diff < diff[i])
            max_diff = diff[i];
    }
    return max_diff;
}

Example
input = 
Time Complexity: O(n)
Auxiliary Space: O(n)

Method 5 - Optimizing the diff approach
We can modify the above method to work in O(1) extra space. Instead of creating an auxiliary array, we can calculate diff and max sum in same loop. Following is the space optimized version.

int maxDiff (int arr[], int n)
{
    // Initialize diff, current sum and max sum
    int diff = arr[1]-arr[0];
    int curr_sum = diff;
    int max_sum = curr_sum;
 
    for(int i=1; i<n-1; i++)
    {
        // Calculate current diff
        diff = arr[i+1]-arr[i];
 
        // Calculate current sum
        if (curr_sum > 0)
           curr_sum += diff;
        else
           curr_sum = diff;
 
        // Update max sum, if needed
        if (curr_sum > max_sum)
           max_sum = curr_sum;
    }
 
    return max_sum;
}

Time Complexity: O(n), Auxiliary Space: O(1)

Method 6 -  Dynamic programming (Preferred and easy :))
But wait a minute - we can do even better than this! Let's think about solving this problem using dynamic programming. The idea will be to think about the problem as follows. Suppose that we knew the answer to the problem after looking at the first k elements. Could we use our knowledge of the (k+1)st element, combined with our initial solution, to solve the problem for the first (k+1) elements? If so, we could get a great algorithm going by solving the problem for the first element, then the first two, then the first three, etc. until we'd computed it for the first n elements.
Let's think about how to do this. If we have just one element, we already know that it has to be the best buy/sell pair. Now suppose we know the best answer for the first k elements and look at the (k+1)st element. Then the only way that this value can create a solution better than what we had for the first k elements is if the difference between the smallest of the first k elements and that new element is bigger than the biggest difference we've computed so far. So suppose that as we're going across the elements, we keep track of two values - the minimum value we've seen so far, and the maximum profit we could make with just the first k elements. Initially, the minimum value we've seen so far is the first element, and the maximum profit is zero. When we see a new element, we first update our optimal profit by computing how much we'd make by buying at the lowest price seen so far and selling at the current price. If this is better than the optimal value we've computed so far, then we update the optimal solution to be this new profit. Next, we update the minimum element seen so far to be the minimum of the current smallest element and the new element.

Since at each step we do only O(1) work and we're visiting each of the n elements exactly once, this takes O(n) time to complete! Moreover, it only uses O(1) auxiliary storage. This is as good as we've gotten so far!
As an example, on your inputs, here's how this algorithm might run. The numbers in-between each of the values of the array correspond to the values held by the algorithm at that point. You wouldn't actually store all of these (it would take O(n) memory!),

Time - O(n), Space - O(1) solution:

public static int findMaxProfit(int[] stockPriceSamples) {
 int maxProfit = 0;
 int minTillNow = stockPriceSamples[0];
 for (int i = 0; i < stockPriceSamples.length; i++) {
  int profit = stockPriceSamples[i] - minTillNow;
  maxProfit = Math.max(profit, maxProfit);
  minTillNow = Math.min(stockPriceSamples[i], minTillNow);
 }
 return maxProfit;
}

Example
input = {5        10         4         6        7}
i = 0, maxProfit = 0, minTillNow=5
i = 1, maxProfit=5, minTillNow=5
i= 2, maxProfit = 5,minTillNow=4
i=3,maxProfit=5,minTillNow=4
i= 4,maxProfit=5,minTillNow=5


References

• http://stackoverflow.com/questions/7086464/maximum-single-sell-profit
• http://www.geeksforgeeks.org/maximum-difference-between-two-elements/
• https://programming4interviews.wordpress.com/2012/02/27/maximize-the-single-sell-profit-of-a-stock/

Read More

Given an array filled with char elements, find the max length of continuous white space

Problem

Given array filled with char elements, can you suggest a most efficient way to find the max length of continuous white space?

Solution

Scan the array left to right, keep a count of white space. When you reach a non-whitespace character, check that count against the current max; if it's higher, it becomes the new max. Set the count back to zero, continue scanning.

Time complexity - O(n)
This is O(n) and you can't really do better because you have to touch each element at least once.

But of-course we can optimize it. Consider the answer given here, we can follow following solution:

Scan the array from left to right, keep a count of white space. When you reach a non-whitespace character, check that count against the current max; if it's higher, it becomes the new max. Skip forwards this max number in the array - if it is not whitespace you know the interval cannot contain the max whitespace. Otherwise search backwards to where whitespace started - find that set your count and continue from where you had previously skipped to.
I believe worst case performance of this would be O(n) and best case would be O(sqrt(n)) for the case where there is a sqrt(n) start of whitespace followed by non-whitespace on every skip point (causing repeated skipping to the end of the array).
 

 

References

• http://stackoverflow.com/questions/5373461/a-question-from-morgan-stanleys-interview

Read More

Finding the biggest difference between sorted array values

Problem

finding the biggest difference between sorted array values

Example 
Consider the array : 
var array = array(1,4,7,8,12,15);
The values in the array will always be integers and is sorted, and elements may repeat.

Now, we want to print out the biggest step in the array. step is difference between adjacent element:
step array - (-,3,3,1,4,3)

The biggest step is 4, between 8 and 12.


Solution

Method 1- Brute force

var max=0;
for (i=1; i<array.length; i++)
    max = Math.max(max,array[i]-array[i-1]);

Reference - stackoverflow

Read More

Stack with find-min/find-max in O(1) time

Problem

Stack with find-min/find-max in O(1) time

Solution

Method 1 - using extra stacks for min and max
The basic idea of the solution can be found here.

Here instead of 2 stacks we will be using 3 stacks -1 stack with normal elements, 1 with only max elements and 1 with min element.
Now the operations will be following  :
push:
- If the element being pushed is less than the top element of 'min_stack' then push it on 'min_stack' as well.
- Else, push the top element of 'min_stack' again on 'min_stack'. Similarly for max_stacks

pop:
- Every time you pop an element from the original stack, pop from 'min_stack' as well.

Example:
Suppose, elements are pushed in the following order: 7 3 5 8 9 1 2 8

original_stack                min_stack                   max_stack
        8                                 1                       8

        2                                 1                       7

        1                                 1                       7

        9                                 3                       7

        8                                 3                       7

        5                                 3                       7

        3                                 3                       7

        7                                 7                       7

Now the pop will result in popping of 8 from original stack, 1 from min stack and 8 from max stack. Now if you try to get minimum, you have to just say min_stack.peek() or for max max_stack.peek().

But currently we are using 3 stacks, but can we do better?

Method 2 - Optimizing method 1
Although the above method is right, but we can still do better. If the stack has lot of elements, then we are wasting a lot of space. However, we can save this useless space as follow:

Instead of saving min(or max) value with each element, we can use two stacks. Because change in the minimum(or maximum) value will not be so frequent, we push the min(or max) value to its respective stack only when the new value is <=(or >=) to the current min(or max) value.

public class StackWithMinMax extends Stack<Integer> {

    private Stack<Integer> minStack;
    private Stack<Integer> maxStack;

    public StackWithMinMax () {
        minStack = new Stack<Integer>();    
        maxStack = new Stack<Integer>();    
    }

    public void push(int value){
        if (value <= min()) { // Note the '=' sign here
            minStack.push(value);
        }

        if (value >= max()) {
            maxStack.push(value);
        }

        super.push(value);
    }

    public Integer pop() {
        int value = super.pop();

        if (value == min()) {
            minStack.pop();         
        }

        if (value == max()) {
            maxStack.pop();         
        }

        return value;
    }

    public int min() {
        if (minStack.isEmpty()) {
            return Integer.MAX_VALUE;
        } else {
            return minStack.peek();
        }
    }

    public int max() {
        if (maxStack.isEmpty()) {
            return Integer.MIN_VALUE;
        } else {
            return maxStack.peek();
        }
    }
}

Example

Stack : MinStack : MaxStack

7         7         7
4         4         7
5         1         8 (TOP)
6         1 (TOP)         
7
8                 
1                  
1                  
7
2
4
2 (TOP)     

Thanks
Reference - stackoverflow

Read More

Find the minimum and maximum in the array

Here are few question we find on finding min and max in the array, but array type changes.

Unsorted 1D array

• Find the maximum (OR minimum) in an array
• Find the maximum AND minimum in an array with min number of comparisons
• Find the max and second maximum in an array (likewise for minimum)
• Find the max and nth max in an array

Rotated Sorted array

• Find the minimum element in the rotated sorted array.
• Find Nth largest element in the rotated sorted array

Read More

Find Maximum Value in the unsorted array

Problem : 
Find Maximum Value in the unsorted array

Solution
Method 1 - Linear search

Here is the code to do that :

public int findMax(int[] numbers)
{
    int max = 0;

    for (int i = 0; i < numbers.length; ++i)
        if (numbers[i] > max) max = numbers[i];

    return max;
}

So, in worst case the number of comparisons will be (n-1).

Time complexity - O(n)

Read More

Find kth largest in an Array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/kth-largest-element-in-an-array/.

Problem : 

 You have an array of numbers; you need to find the k-th largest in the arra

 Solution

Method 1 - Tournament principle
We have to find the element which has competed with largest element, and is just (k-1)th level.We have discussed this principle here.

Method 2 - Using max heap

Consider the array of length n. Here is the algo : 

• Build a max heap in O(n) ; 
• Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. So total time complexity = O(k logn) 
• To understand building MAX heap in O(n) check heap.

Method 3 - Modified bubble sort running k times
1) Modify Bubble Sort to run the outer loop at most k times.
2) Print the last k elements of the array obtained in step 1.
Time Complexity: O(nk)
Like Bubble sort, other sorting algorithms like Selection Sort can also be modified to get the k largest elements.

Method 4 - Use temporary array
K largest elements from arr[0..n-1]
1) Store the first k elements in a temporary array temp[0..k-1].
2) Find the smallest element in temp[], let the smallest element be min.
3) For each element x in arr[k] to arr[n-1]
If x is greater than the min then remove min from temp[] and insert x.
4) Print final k elements of temp[]
Time Complexity: O((n-k)*k). If we want the output sorted then O((n-k)*k + klogk)

Method 5 - Use Min Heap
This method is mainly an optimization of method 4. Instead of using temp[] array, use Min Heap.
1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
       a) If the element is greater than the root then make it root and call heapify for MH
       b) Else ignore it.
// The step 2 is O((n-k)*logk)
3) Finally, MH has k largest elements and root of the MH is the kth largest element.
Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)
All of the above methods can also be used to find the kth largest (or smallest) element.


Method 6 - Use Sorting
1) Sort the elements in descending order in O(nLogn)
2) Print the first k numbers of the sorted array O(k).
Time complexity: O(nlogn)

Method 7 - Use Order Statistics
If you want a true O(n) algorithm, as opposed to O(kn) or something like that, then you should use quickselect (it's basically quicksort where you throw out the partition that you're not interested in). This is called finding the k-th order statistics.

There's a very simple randomized algorithm (called quickselect) taking O(n) average time, and a pretty complicated non-randomized algorithm taking O(n) worst case time. There's some info on Wikipedia, but it's not very good.
Everything you need is in these powerpoint slides. Also, refer quicksort and randomized selection to find introductory help on randomized algorithm.


Just to extract the basic algorithm of the O(n) worst-case algorithm:

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

The algorithm is discussed in detail here.

Method 8 - Compare 3 elements if N=3 (like wise for N)

int third_biggest(int *arr, int size)
{
 int first = INT_MIN, second = INT_MIN, third = INT_MIN;
 for(int i=0;i first)
  {
   third = second;
   second = first;
   first = arr[i];
  }
  else if(arr[i] > second)
  {
   third = second;
   second = arr[i];
  }
  else if(arr[i] > third)
  {
   third = arr[i];
  }
 }
 return third;
}

Ofcourse, method 7 is best :)

Read More

find out the largest and second largest number in an array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-second-largest-element-in-an-array/.

Question: Write an efficient C program to find smallest and second smallest element in an array.

Solution
Method 1 - Compare each element with current max and second max

Algorithm

1) Initialize both first and second smallest as a[0]
   first = second = a[0]
2) Loop through all the elements.
   a) If the current element is greater than firstMax, then update firstMax 
       and secondMax. 
   b) Else if the current element is greater than second then update 
    secondMax

pseudocode

largest = numbers[0];
secondLargest = null
for (i=1 to numbers.length-1) {    
    if numbers[i] > largest {
        secondLargest = largest;
        largest = numbers[i];
    else
        if numbers[i] > secondLargest {
            secondLargest = numbers[i];
        }
    }
}

Time Complexity: O(n)
 Number of comparisons atmost will be 2(N-1)

Method 2 - Tournament principle

The optimal algorithm uses n+log n-2 comparisons. Think of elements as competitors, and a tournament is going to rank them.
First, compare the elements, as in the tree

   |
  / \
 |   |
/ \ / \
x x x x

this takes n-1 comparisons and each element is involved in comparison at most log n times. You will find the largest element as the winner.
The second largest element must have lost a match to the winner (he can't lose a match to a different element), so he's one of the log n elements the winner has played against. You can find which of them using log n - 1 comparisons.

Example-

1. Start with comparing elements of the n element array in odd and even positions and determining largest element of each pair. This step requires n/2 comparisons. Now you've got only n/2 elements. Continue pairwise comparisons to get n/4, n/8, ... elements. Stop when the largest element is found. This step requires a total of n/2 + n/4 + n/8 + ... + 1 = n-1 comparisons.
2. During previous step, the largest element was immediately compared with log₂(n) other elements. You can determine the largest of these elements in log₂(n)-1 comparisons. That would be the second-largest number in the array.

 So, looking at the tree above, 9 is the winner, but we find 2nd winner on level 2 and so on.

From the above picture we can see that we have found the max in the array. Now we know 9 is MAX but we can't say 7 is SECOND MAX since that would be wrong. Number of Comparison's to find MAX = (n/2) + logn(n) = (n-1) in the above case so the above algo is also optimal for finding MAX ; since conventional algo also takes the same. To find SECOND MAX take the players that were directly defeated by MAX. i.e. 9 DIRECTLY DEFEATED BY MAX = 8, 3, 7 If we play the above tournament among 8, 3, 7 we get 8 as second MAX we for this tournament we needed just 2 comparison's Total comparisons to find MAX and second MAX using tournament principle = (n/2) + log(n) + log(n) = (n-1) + log(n) Now to find kth MAX we can play (k/2) such tournaments since in one tournament we get MAX and second MAX..then exclude them and play the tournament again(k/2) times So total comparisons to find kth MAX using above method = (k/2) ((n-1) + log(n)) However in the conventional algo it would be (k/2 passes of array)(2n comparisons to find MAX and second MAX) = k * n So tournament algo is more optimal eg:: if k = 4 and n = 8 Comparison's by conventional algo = 4 * 8 = 32 Comparison's by Tournament algo = (4/2) ((7) + 3) = 2 * 10 = 20  

Here is the code for tournament principle:

Here is the solution taken from stackoverflow:
To make things work, there are two assumptions:
1) number of elements in the array is the power of 2
2) there are no duplicates in the array
The whole process consists of two steps:
1. building a 2D array by comparing two by two elements. First row in the 2D array is gonna be the entire input array. Next row contains results of the comparisons of the previous row. We continue comparisons on the newly built array and keep building the 2D array until an array of only one element (the largest one) is reached.
2. we have a 2D-array where last row contains only one element: the largest one. We continue going from the bottom to the top, in each array finding the element that was "beaten" by the largest and comparing it to the current "second largest" value. To find the element beaten by the largest, and to avoid O(n) comparisons, we must store the index of the largest element in the previous row. That way we can easily check the adjacent elements. At any level (above root level),the adjacent elements are obtained as:

leftAdjacent = rootIndex*2
rightAdjacent = rootIndex*2+1,

where rootIndex is index of the largest(root) element at the previous level.

public static Integer findSecondLargest(List<Integer> list) {
        if (list == null) {
            return null;
        }
        if (list.size() == 1) {
            return list.get(0);
        }
        List<List<Integer>> structure = buildUpStructure(list);
        System.out.println(structure);
        return secondLargest(structure);

    }

    public static List<List<Integer>> buildUpStructure(List<Integer> list) {
        List<List<Integer>> newList = new ArrayList<List<Integer>>();
        List<Integer> tmpList = new ArrayList<Integer>(list);
        newList.add(tmpList);
        int n = list.size();
        while (n>1) {
            tmpList = new ArrayList<Integer>();
            for (int i = 0; i<n; i=i+2) {
                Integer i1 = list.get(i);
                Integer i2 = list.get(i+1);
                tmpList.add(Math.max(i1, i2));
            }
            n/= 2;
            newList.add(tmpList);   
            list = tmpList;
        }
        return newList;
    }

    public static Integer secondLargest(List<List<Integer>> structure) {
        int n = structure.size();
        int rootIndex = 0;
        Integer largest = structure.get(n-1).get(rootIndex);
        List<Integer> tmpList = structure.get(n-2);
        Integer secondLargest = Integer.MIN_VALUE;
        Integer leftAdjacent = -1;
        Integer rightAdjacent = -1;
        for (int i = n-2; i>=0; i--) {
            rootIndex*=2;
            tmpList = structure.get(i);
            leftAdjacent = tmpList.get(rootIndex);
            rightAdjacent = tmpList.get(rootIndex+1); 
            if (leftAdjacent.equals(largest)) {
                if (rightAdjacent > secondLargest) {
                    secondLargest = rightAdjacent;
                }
            }
            if (rightAdjacent.equals(largest)) {
                if (leftAdjacent > secondLargest) {
                    secondLargest = leftAdjacent;
                }
                rootIndex=rootIndex+1;
            }
        }

        return secondLargest;
    }

Reference - stackoverflow

Read More

How to find max. and min. in array using minimum comparisons?

Problem : Given an array of integers find the max. and min. using minimum comparisons.

Solution
Method 1 (Naive) - Iterate through the array, and update min and max pointers

1. Iterate through the array, select element a
2. Update min by comparing (min, a)
3. Update max by comparing (max, a)

Number of comparison here will be ~2N, if N is number of element.
Time complexity will be O(n) though.

Method 2 - Pick 2 elements at time, compare them and compare them with corresponding min and max

1. Pick 2 elements(a, b), compare them. (say a > b)
2. Update min by comparing (min, b)
3. Update max by comparing (max, a)

This way you would do 3 comparisons for 2 elements, amounting to 3N/2 total comparisons for N elements.(Actually it is 3N/2 if N is even, and 3(N-1)/2 if N is odd)

Example
Consider

A = [a1, a2, a3, a4, a5]

Compare a1 & a2 and calculate min12, max12:

if (a1 > a2)
  min12 = a2
  max12 = a1
else
  min12 = a1
  max12 = a2

Similarly calculate min34, max34. Since a5 is alone, keep it as it is...

This way you would do 3 comparisons for 2 elements, amounting to 3N/2 total comparisons for N elements.


Iterative solution

class Pair 
{
   public int min;
   public int max;
}
public Pair getMinMax(int arr[], int n)
{
  Pair minmax;    
  int i; 
 
  // If array has even number of elements then
  //  initialize the first two elements as minimum and
  //  maximum 
  if (n%2 == 0)
  {        
    if (arr[0] > arr[1])    
    {
      minmax.max = arr[0];
      minmax.min = arr[1];
    } 
    else
    {
      minmax.min = arr[0];
      minmax.max = arr[1];
    }
    i = 2;  // set the startung index for loop 
  } 
 
   // If array has odd number of elements then
   // initialize the first element as minimum and
   // maximum 
  else
  {
    minmax.min = arr[0];
    minmax.max = arr[0];
    i = 1;  // set the startung index for loop 
  }
   
  // In the while loop, pick elements in pair and
  //   compare the pair with max and min so far    
  while (i < n-1) 
  {         
    if (arr[i] > arr[i+1])         
    {
      if(arr[i] > minmax.max)       
        minmax.max = arr[i];
      if(arr[i+1] < minmax.min)         
        minmax.min = arr[i+1];       
    }
    else        
    {
      if (arr[i+1] > minmax.max)       
        minmax.max = arr[i+1];
      if (arr[i] < minmax.min)         
        minmax.min = arr[i];       
    }       
    i += 2; //Increment the index by 2 as two
            //   elements are processed in loop 
  }           
 
  return minmax;
}    

Method 3 - Tournament Method
This is similar to previous method, where we were taking 2 elements at a time. Here we are doing this in local subarray recursively and returning elements accordingly.

Pair MaxMin(array, array_size)
   if array_size = 1
      return element as both max and min
   else if arry_size = 2
      one comparison to determine max and min
      return that pair
   else    // array_size  > 2 
      recur for max and min of left half
      recur for max and min of right half
      one comparison determines true max of the two candidates
      one comparison determines true min of the two candidates
      return the pair of max and min

Here is the code

void minmax (int[] a, int left, int right, int min, int max) {
  int lmin, lmax, rmin, rmax, mid;
  if (left==right) {
    min = a[left];
    max = a[right];
  } else if (right == left+ 1) {
    if (a[left] > a[right]) {
      min = a[right];
      max = a[left];
    } else {
      min = a[left];
      max = a[right];
    }
  } else {
    mid = (left+right) / 2;
    minmax(a,left, mid, lmin, lmax);
    minmax(a, mid + 1,right, rmin, rmax);
    min = (lmin > rmin) ? rmin : lmin;
    max = (lmax > rmax) ? lmax : rmax;
  }
}

Thanks.

References -stackoverflow , geeksforgeeks

Read More

Finding the max repeated element in an array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-most-frequent-element-in-the-array/.

Problem : Find the element which occurs maximum number of times.

METHOD 1 : Sorting the array and scanning the array
The simple solution is to
1) Sort the array
2) Scan the array such that keep the track of the elements which occurred max number of times

METHOD 2 : Using Binary Search Tree

We can have a binary search tree with an extra field count, which indicates the number of times an element appeared in the input. 
Node of the Binary Search Tree (used in this approach) will be as follows.

struct tree
{
  int element;
  int count;
}BST;

1) Insert elements in BST one by one and if an element is already present then increment the count of the node.
2) Now do the inorder traversal on the tree, keeping track of the count and value of max element in the tree.

Time complexity - O(n) + O(n) ≈ O(n). First for contructing the tree and second for inorder traversal.

Space complexity - O(2n)  ≈ O(n), since every node needs 2 extra pointers.

METHOD 3 : Using Hashtable
Use a counter for each elements, as value and key as the element in the hashtable. At the end just retun the element having max counter.

Time complexity - O(n) and space complexity O(n) needed for storing in hashtable.

Read More

Maximum value in a Sliding Window

Problem Statement
Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position.

Example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.

Window position                Max 
---------------               ----- 
[1  3  -1] -3  5  3  6  7       3  
1  [3  -1  -3] 5  3  6  7       3  
1  3  [-1  -3  5] 3  6  7       5  
1  3  -1  [-3  5  3] 6  7       5  
1  3  -1  -3  [5  3  6] 7       6  
1  3  -1  -3  5  [3  6  7]      7

Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]

Example 2
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
w= 3
Output :
3 3 4 5 5 5 6

Solution

Method 1: Brute force

The obvious solution with run time complexity of O(nw) is definitely not efficient enough. Every time the window is moved, we have to search for the maximum from w elements in the window.
Code(Java):

void windowMaxBrute(int arr[], int w)
{
    int j, max;
    int n = arr.length;
    int b[] = new int[arr.length];
    int k=0;//tracker for array b
    for (int i = 0; i <= n-w; i++)
    {
        max = arr[i];
    
        for (j = 1; j < w; j++)
        {
            if (arr[i+j] > max)
                max = arr[i+j];
        }
        b[k] = max;
    }
}

Time complexity - O(n)
Can we do better?

Method 2z : Using Heap (will not work)

Of-course we can do better.  The word max value rings the bell in our head - we can use priority queue?

A heap data structure quickly comes to mind. We could boost the run time to approximately O(n lg w) (Note that I said approximately because the size of the heap changes constantly and averages about w). Insert operation takes O(lg w) time, where w is the size of the heap. However, getting the maximum value is cheap, it merely takes constant time as the maximum value is always kept in the root (head) of the heap.

As the window slides to the right, some elements in the heap might not be valid anymore (range is outside of the current window). How should you remove them? You would need to be somewhat careful here. Since you only remove elements that are out of the window’s range, you would need to keep track of the elements’ indices too. Finding the element to delete in the heap, will take O(w) and O(lgW) time for heapify operation. So, time complexity for n elements, will be again O(n*(w+lgw)) = O(nw), which is same as brute force.

But there are couple of solutions. Lets discuss them one by one. Can we use similar structure to heap, like priority queue?

Method 2a - Maximal value in a queue

A window can be viewed as a queue. When it slides, a number is pushed into its back, and its front is popped off. Therefore, the problem is solved if we can get the maximal value of a queue. There are no straightforward approaches to getting the maximal value of a queue. However, there are solutions to get the maximal value of a stack, which is similar to the solution introduced in the blog “Stack with Function min()”. Additionally, a queue can also be implemented with two stacks (details are discussed in another blog “Queue implemented with Two Stacks”).  If a new type of queue is implemented with two stacks, in which a function max() is defined to get the maximal value, the maximal value in a queue is the greater number of the two maximal numbers in two stacks. Lets call this queue QMax.
Here are the steps:

1. Enqueue w elements into the QMax. Time complexity = O(w)
2. Get the max element from the QMax, and print it, which takes constant time. O(1)
3. Dequeue element from QMax. O(1)
4. Enqueue next element in QMax, O(1)
5. Repeat step 2, 3, 4 until we reach end of array.

Time complexity = O(w + n+n+n) = O(n+w) This solution is workable. However, we may not have enough time to write all code to implement our own queue and stack data structures during interviews. Let us continue exploring a more concise solution.

Method 2b - Saving the maximal value into the front of a queue

Instead of pushing every numbers inside a sliding window into a queue, we try to push the candidates of maximum only into a queue.

Let us take the array {2, 3, 4, 2, 6, 2, 5, 1} as an example and window size as 3 to analyze the solution step by step.

• The first number in the array is 2, we push it into a queue. 
• The second number is 3, which is greater than the previous number 2. The number 2 should be popped off, because it is less than 3 and it has no chance to be the maximal value. There is only one number left in the queue when we pop 2 at the back and push 3 at the back. 
• The operations are similar when we push the next number 4. There is only a number 4 remaining in the queue. Now the sliding window already has three elements, we can get the maximum value at the front of the queue.
• We continue to push the fourth number i.e. 2.  It is pushed at the back of queue, because it is less than the previous number 4 and it might be a maximal number in the future when the previous numbers are popped off. There are two numbers, 4 and 2, in the queue, and 4 is the maximum. 
• The next number to be pushed is 6. Since it is greater than the existing numbers, 4 and 2, these two numbers can be popped off because they have no chance to be the maximum. Now there is only one number in the queue, which is 6, after the current number is pushed. Of course, the maximum is 6.  
• The next number is 2, which is pushed into the back of the queue because it is less than the previous number 6. There are two numbers in the queue, 6 and 2, and the number 6 at the front of the queue is the maximal value. 
• It is time to push the number 5. Because it is greater than the number 2 at the back of the queue, 2 is popped off and then 5 is pushed. There are two numbers in the queue, 6 and 5, and the number 6 at the front of the queue is the maximal value. Now let us push the last number 1. It can be pushed into the queue. 

  It is noticeable that the number at the front is beyond the scope the current sliding window, and it should be popped off.  How do we know whether the number at the front of the queue is out of sliding window? Rather than storing numbers in the queue directly, we can store indices instead. If the distance between the index at the front of queue and the index of the current number to be pushed is greater than or equal to the window size, the number corresponding to be the index at the font of queue is out of sliding window.

The analysis process above is summarized in Table 2.

Step	Number to Be Pushed	Numbers in Sliding Window	Indices in queue	Maximum in Window
1	2	2	0(2)
2	3	2, 3	1(3)
3	4	2, 3, 4	2(4)	4
4	2	3, 4, 2	2(4), 3(2)	4
5	6	4, 2, 6	4(6)	6
6	2	2, 6, 2	4(6), 5(2)	6
7	5	6, 2, 5	4(6), 6(5)	6
8	1	2, 5, 1	6(5), 7(1)	5

Table 2: The process to get the maximal number in all sliding windows with window size 3 in the array {2, 3, 4, 2, 6, 2, 5, 1}. In the column “Indices in queue”, the number inside a pair of parentheses is the number indexed by the number before it in the array.

Code (c++)
We can implement a solution based on the analysis above. Some sample code in C++ is shown below, which utilizes the type deque of STL.

 vector<int> maxInWindows(const vector<int>& numbers, int windowSize)
{
    vector<int> maxInSlidingWindows;
    if(numbers.size() >= windowSize && windowSize > 1)
    {
        deque<int> indices;

        for(int i = 0; i < windowSize; ++i)
        {
            while(!indices.empty() && numbers[i] >= numbers[indices.back()])
                indices.pop_back();

            indices.push_back(i);
        }

        for(int i = windowSize; i < numbers.size(); ++i)
        {
            maxInSlidingWindows.push_back(numbers[indices.front()]);

            while(!indices.empty() && numbers[i] >= numbers[indices.back()])
                indices.pop_back();
            if(!indices.empty() && indices.front() <= i - windowSize)
                indices.pop_front();

            indices.push_back(i);
        }
        maxInSlidingWindows.push_back(numbers[indices.front()]);
    }

    return maxInSlidingWindows;
}

Method 2c - Another solution to get the maximum of a queue

As we mentioned before, a sliding window can be viewed as a queue. Therefore, we can implement a new solution to get the maximal value of a queue based on the second solution to get the maximums of sliding windows.

The following is the sample code:

 template<typename T> class QueueWithMax
{
public:
    QueueWithMax(): currentIndex(0)
    {
    }

    void push_back(T number)
    {
        while(!maximums.empty() && number >= maximums.back().number)
            maximums.pop_back();

        InternalData internalData = {number, currentIndex};
        data.push_back(internalData);
        maximums.push_back(internalData);

        ++currentIndex;
    }

    void pop_front()
    {
        if(maximums.empty())
            throw new exception("queue is empty");

        if(maximums.front().index == data.front().index)
            maximums.pop_front();

        data.pop_front();
    }

    T max() const
    {
        if(maximums.empty())
            throw new exception("queue is empty");

        return maximums.front().number;
    }

private:
    struct InternalData
    {
        T number;
        int index;
    };

    deque<InternalData> data;
    deque<InternalData> maximums;
    int currentIndex;
};

Since this solution is similar to the second solution to get maximums of sliding windows, we won’t analyze the process step by step, and leave it as an exercise if you are interested.

Method 3 - Use Self-Balancing BST

This is similar to 2z.

1. Pick first k elements and create a Self-Balancing Binary Search Tree (BST) of size w.
2. Run a loop for i = 0 to n – w
   
   1. Get the maximum element from the BST, and print it.
   2. Search for arr[i] in the BST and delete it from the BST.
   3. Insert arr[i+w] into the BST.

This solution is similar to 2z(using heap), but note that delete is less costly operation, as instead of O(w), we will be taking O(lg w).

Time Complexity:
Time Complexity of step 1 is O(w lg(w)).
Time Complexity of steps 2(a), 2(b) and 2(c) is O(Logk). Since steps 2(a), 2(b) and 2(c) are in a loop that runs n-k+1 times, time complexity of the complete algorithm is O(wLogw + (n-k+1)*Logw) which can also be written as O(nLogw).

Method 4 - Usint Dequeue

This method is similar to method 2b.
We create a Dequeue, Qi of capacity w, that stores only useful elements of current window of w elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window.
Code(java)

void windowMaxDeque(int arr[],  int w)
{
    // Create a Double Ended Queue, Qi that will store indexes of array elements
    // The queue will store indexes of useful elements in every window and it will
    // maintain decreasing order of values from front to rear in Qi, i.e., 
    // arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order
    Deque <Integer > Qi = new Deque < >(w);
    
    int n = arr.length;
    // Process first w (or first window) elements of array 
    int i;
    for (i = 0; i  < w; ++i)
    {
        // For very element, the previous smaller elements are useless so
        // remove them from Qi
        while ( (!Qi.empty()) && arr[i]  >= arr[Qi.back()])
            Qi.pop_back();  // Remove from rear
 
        // Add new element at rear of queue
        Qi.push_back(i);
    }
 
    // Process rest of the elements, i.e., from arr[w] to arr[n-1]
    for ( ; i  < n; ++i)
    {
        // The element at the front of the queue is the largest element of
        // previous window, so print it
        cout  < < arr[Qi.front()]  < < " ";
 
        // Remove the elements which are out of this window
        while ( (!Qi.empty()) && Qi.front()  <= i - w)
            Qi.pop_front();  // Remove from front of queue
 
        // Remove all elements smaller than the currently
        // being added element (remove useless elements)
        while ( (!Qi.empty()) && arr[i]  >= arr[Qi.back()])
            Qi.pop_back();
 
         // Add current element at the rear of Qi
        Qi.push_back(i);
    }
 
    // Print the maximum element of last window
    System.out.println(arr[Qi.front()]);
}
 
// Driver program to test above functions
public static void main(String[] args)
{
    int arr[] = {12, 1, 78, 90, 57, 89, 56};
    int w = 3;
    windowMaxDeque(arr, w);
}

Please suggest, if you have some other methods.
Source

• http://myqc.wordpress.com/2012/08/13/amazon-interview-questions-cheatsheet/
• http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/ 
• http://articles.leetcode.com/sliding-window-maximum/ 

Read More

Maximum continuous sum subarray problem

Problem

You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.
EXAMPLE
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i.e., {3, -2, 4})

Solution 

Method 1 - Brute force
The outer loop picks the beginning element, the inner loop finds the maximum possible sum with first element picked by outer loop and compares this maximum with the overall maximum. Finally return the overall maximum. The time complexity of the Naive method is O(n^2).

Method 2 - Divide and conquer
1) Divide the given array in two halves
2) Return the maximum of following three
….a) Maximum subarray sum in left half (Make a recursive call)
….b) Maximum subarray sum in right half (Make a recursive call)
….c) Maximum subarray sum such that the subarray crosses the midpoint
The lines 2.a and 2.b are simple recursive calls. How to find maximum subarray sum such that the subarray crosses the midpoint? We can easily find the crossing sum in linear time. The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1. Finally, combine the two and return.

int maxCrossingSum(int arr[], int l, int m, int h)
{
    // Include elements on left of mid.
    int sum = 0;
    int leftSum = Integer.MIN;
    for (int i = m; i >= l; i--)
    {
        sum = sum + arr[i];
        if (sum > leftSum)
          leftSum = sum;
    }
 
    // Include elements on right of mid
    sum = 0;
    int rightSum = Integer.MIN;
    for (int i = m+1; i <= h; i++)
    {
        sum = sum + arr[i];
        if (sum > rightSum)
          rightSum = sum;
    }
 
    // Return sum of elements on left and right of mid
    return leftSum + rightSum;
}
 
// Returns sum of maxium sum subarray in aa[l..h]
int maxSubArraySum(int arr[], int l, int h)
{
   // Base Case: Only one element
   if (l == h)
     return arr[l];
 
   // Find middle point
   int m = (l + h)/2;
 
   /* Return maximum of following three possible cases
      a) Maximum subarray sum in left half
      b) Maximum subarray sum in right half
      c) Maximum subarray sum such that the subarray crosses the midpoint */
   return Math.max(maxSubArraySum(arr, l, m),
              maxSubArraySum(arr, m+1, h),
              maxCrossingSum(arr, l, m, h));
}

Time Complexity:  O(nLog n)
maxSubArraySum() is a recursive method and time complexity can be expressed as following recurrence relation.
T(n) = 2T(n/2) + Θ(n)
The above recurrence is similar to Merge Sort and can be solved either using Recurrence Tree method or Master method. It falls in case II of Master Method and solution of the recurrence is Θ(nLogn).

Method 3 - Dynamic Programming using Kadane's algorithm (Best)
This problem can be solved by using a modified version of Kadane's Algorithm. The strategy is to calculate the sum of each subarray and keep track of the sum, the start index and the end index of the subarray that gives the largest sum. Moreover, we calculate the sum of a subarray by adding the sum of the previous subarray with an additional element. For example, to calculate the sum of {5, 2, -1}, we add the sum of {5, 2}, which is 7, to the value of the next element, which is -1.

Kadane's algorithm/pseudocode

Initialize:
    maxSoFar = 0
    maxEndingHere = 0

Loop for each element of the array
  (a) maxEndingHere = maxEndingHere + a[i]
  (b) if(maxEndingHere < 0)
            maxEndingHere = 0
  (c) if(maxSoFar < maxEndingHere)
            maxSoFar = maxEndingHere
return maxSoFar

In simpler terms, iterate over the array and have 2 checks:

• if greater intermediate sum is found, store it constituents as a temporary result;
• independently, if sum got negative, reset it to 0 and prepare to build a new sequence from next scan position.

Code in java

public static void findMaxSumSequence (int inputArray[])
{
    if (inputArray == null || inputArray.length == 0)
        throw new IllegalArgumentException("Array is empty");

    int size = inputArray.length;

    int maxSum = inputArray[0];
    int maxStartIndex = 0;
    int maxEndIndex = 0;

    int curSum = inputArray[0];
    int curStartIndex = 0;


    for (int i = 1; i < size; i++)
    {
        if (curSum < 0)
        {
            curSum = 0;
            curStartIndex = i;
        }

        curSum = curSum + inputArray[i];

        if (curSum > maxSum)
        {
            maxSum = curSum;
            maxStartIndex = curStartIndex;
            maxEndIndex = i;
        }
    } 

    out.println( "Start index: " + maxStartIndex + " End index: " 
            + maxEndIndex + " Max sum: " + maxSum );
}

Time Complexity: O(n)

Explanation
This method accepts an array and its size as arguments. It prints out the start index, end index and the sum of the subarray that yields the max sum. Here are the main steps:

1. First, check if the array size is 0. If it is so, we throw an exception because there is nothing we need to do when the array is null.
2. Then, initialize variables: maxSum is the largest sum found. maxStartIndex and maxEndIndex are respectively the start index and end index of the subarray that yields the max sum. curSum is the sum of the current subarray that we're examining. curStartIndex is the start index of the current subarray we're checking.
3. Next, we loop through the array and start calculating the sum of subarrays one after another:
   
   If the sum of the current subarray is less than 0, we reset curSum to 0. Why? If the last subarray's sum is negative, we will only decrease the next subarray's sum by adding the previous subarray's sum with an additional number. For example, if the previous subarray's sum is -2, and the next element is 3, it's better to reset the sum to 0 and add 3 into 0 than to add -2 to 3.
   
   curSum = curSum + inputArr[i] calculates the sum of the current subarray by adding the sum of the previous subarray with the next value in the array.
   
   After that, if the sum of the current subarray is greater than the max sum then we replace the max sum with the sum of the current subarray. We also change the maxStartIndex to the start index of the current subarray and the maxEndIndex to the current index i.
   
   When the loop ends, maxSum will contain the largest sum found. maxEndIndex and maxStartIndex contain respectively the end and start index of the subarray that gives the largest sum. Thus, we just have to print out those values.

If you have any comment or another solution to this problem, please post in the comment below. I would love to learn about it. Thanks for reading and until next post!

References

• http://tianrunhe.wordpress.com/2012/05/17/maximum-continuous-sum-problem/
• http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
• http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/

Read More

Majority element in the array

Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Problem: Given an array consisting of N integers, find the number with the maximum occurrences, i.e. majority element, given the assumption that the number occurs more than N/2 times in the array.

Example
I/P : 3 3 4 2 4 4 2 4 4
O/P : 4

I/P : 3 3 4 2 4 4 2 4
O/P : NONE

METHOD 1 (Basic)
The basic solution is to have two loops and keep track of maximum count for all different elements. If maximum count becomes greater than n/2 then break the loops and return the element having maximum count. If maximum count doesn’t become more than n/2 then majority element doesn’t exist.
Time Complexity: O(n*n).
Auxiliary Space : O(1).

METHOD 2 (Using Binary Search Tree)

We can have a binary search tree with an extra field count, which indicates the number of times an element appeared in the input. 
Node of the Binary Search Tree (used in this approach) will be as follows.

struct tree
{
  int element;
  int count;
}BST;

Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
The method works well for the cases where n/2+1 occurrences of the majority element is present in the starting of the array, for example {1, 1, 1, 1, 1, 2, 3, 4}.

Time Complexity: If a binary search tree is used then time complexity will be O(n^2). If a self-balancing-binary-search tree is used then O(nlogn)
Auxiliary Space: O(n)


METHOD 3 (Using Moore’s Voting Algorithm)
Given the assumption that the element occurs more than N/2 times in the array simplifies the solution a lot. This is so because if more than N/2 elements are the same, it implies that all other elements combined are less than N/2. Hence, the difference between the count of majority element and the count of non-majority numbers will always be positive. This approach can significantly simplify our code to the problem.


This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.


In the solution we consider the first element as the majority element and keep the count as 1. Now we compare the second (next) element with this element. If it is the same element we increase the count to 2, else decrease the count to ZERO and keep the first element as the majority element. Check the next element. If it is equal increase the count, else set the majority element to be the given current element and make the count as ONE.


This way, at the end of the traversal of the list, we will have the majority element with us.

Time complexity - As comparison between two elements takes constant time, the code will run in O(n) time where n is the number of elements in the list.

public static void printMajorElement(String[] args) {
  int[] list = new int[] {1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 1, 2, 3, 4, 2, 2, 2};
   
  int count = 1;
  int majorityElement = list[0];
  for(int index = 1; index < list.length; index++) {
   if(majorityElement != list[index]) {
    if(count == 0) {
     majorityElement = list[index];
     count++;
    } else {
     count--;
    }
   } else {
    count++;
   }
  }
   
  System.out.println("Majority Element: " + majorityElement);
 }

Dry running the above program:
Lets consider the array A = {1,2,3,4,2,3,2,1,2,3,4,2,2,2}

Initially, majority element = 1 i.e. list(0), count=1
Now we traverse through the array. As next eleement is 2, we decrement the count to 0 because majorityElement 1 is not equal to list[1];

Now, we have count = 0. Again 1 is not equal to 3 and this time count=0, hence we change majority element to 3, count =1.

Now we have 4, and as 3!=4, we decrement count again.

 Next time 3!=2, we again decrement count, and point majority element to 2, and increment count =2.

Hence we see depending on if count>0, we are getting a majority element.

Thanks.

Read More

IsBST : Check whether the tree provided is BST or not

Problem
This background is used by the next two problems: Given a plain binary tree, examine the tree to determine if it meets the requirement to be a binary search tree. To be a binary search tree, for every node, all of the nodes in its left tree must be <= the node, and all of the nodes in its right subtree must be > the node. Consider the following four examples...

a.  5   -> TRUE

   / \

  2   7

b.  5   -> FALSE, because the 6 is not ok to the left of the 5

   / \

  6   7

c.   5  -> TRUE

    / \

   2   7

  /

1

d.   5  -> FALSE, the 6 is ok with the 2, but the 6 is not ok with the 5

    / \

   2   7

  / \

1     6

Solutions

There are couple of solution to this.

For the first two cases, the right answer can be seen just by comparing each node to the two nodes immediately below it. However, the fourth case shows how checking the BST quality may depend on nodes which are several layers apart -- the 5 and the 6 in that case.
Method 1 - Simple Recursive Solution BUT WRONG

int isBST(struct node* node)
{
  if (node == NULL)
    return 1;
     
  // false if left is > than node 
  if (node->left != NULL && node->left->data > node->data)
    return 0;
     
  // false if right is < than node 
  if (node->right != NULL && node->right->data < node->data)
    return 0;
   
  // false if, recursively, the left or right is not a BST 
  if (!isBST(node->left) || !isBST(node->right))
    return 0;
     
  // passing all that, it's a BST 
  return 1;
}

Here is the test case which shows it fails:

So, what's the correct solution then.

Method 2 - Correct Solution
For each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.

/* Returns true if a binary tree is a binary search tree */
int isBST(struct node* node)
{
  if (node == NULL)
    return(true);
     
  /* false if the max of the left is > than us */
  if (node->left!=NULL && maxValue(node->left) > node->data)
    return(false);
     
  /* false if the min of the right is <= than us */
  if (node->right!=NULL && minValue(node->right) < node->data)
    return(false);
   
  /* false if, recursively, the left or right is not a BST */
  if (!isBST(node->left) || !isBST(node->right))
    return(false);
     
  /* passing all that, it's a BST */
  return(true);
} 

It is assumed that you have helper functions minValue() and maxValue() that return the min or max int value from a non-empty tree.
Min value from BST (more here):

int minValue(struct node* node) {
  struct node current = node;   // loop down to find the leftmost leaf
  while (current->left != NULL) {
    current = current->left;
  }
  return(current->data);
}

Max value from BST:

int maxValue(struct node* node) {
  struct node current = node;   // loop down to find the leftmost leaf
  while (current->right != NULL) {
    current = current->right;
  }
  return(current->data);
}

Time complexity : O(n^2)
(As minValue and maxValue are O(n) )
Space Complexity : O(n) [for stack space, otherwise O(1)]

Method 3 - Efficient solution
 Method 2 above runs slowly since it traverses over some parts of the tree many times. A better solution looks at each node only once. The trick is to write a utility helper function isBSTUtil(struct node* node, int min, int max) that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX — they narrow from there.

// Returns true if the given tree is a binary 
// search tree (efficient version).
int isBST2(struct node* node) {
  return(isBSTUtil(node, INT_MIN, INT_MAX));
} 
// Returns true if the given tree is a BST and its values 
// are >= min and <= max.
int isBSTUtil(struct node* node, int min, int max) {
  if (node==NULL) return(true); 
// false if this node violates the min/max constraint
  if (node->data >max || node->data < min) return(false); 
// otherwise check the subtrees recursively, 
// tightening the min or max constraint
  return   
    isBSTUtil(node->left, min, node->data -1 ) //node->data - 1 for distinct values
    && 
    isBSTUtil(node->right, node->data+1, max)  );// for distinct values
}

Time complexity : O (n)
Space Compexity : O(n) for stack space (Otherwise O(1) as we have not used any array etc)

Method 4 - Inorder traversal (with and without aux array)
You can read about inorder traversal here.
Using aux array-
Here are the steps we have to follow:

1. Do In-Order Traversal of the given tree and store the result in a temp array.
2. Check if the temp array is sorted in ascending order, if it is, then the tree is BST.

Time Complexity: O(n)
Space Complexity - O(n)

Without using aux array
We can avoid the use of Auxiliary Array. While doing In-Order traversal, we can keep track of previously visited node. If the value of the currently visited node is less than the previous value, then tree is not BST. Here is the code:

bool isBST(struct node* root)
{
    static struct node *prev = NULL;
     
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
          return false;
 
        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
          return false;
 
        prev = root;
 
        return isBST(root->right);
    }
 
    return true;
}

The use of static variable can also be avoided by using reference to prev node as a parameter. Also, we are using calling isBST with right node after setting prev to root as we care about the next node of that root.

Method 5 - Iterative solution using BFS

The below code is just a modified version of the standard non-recursive Breadth First Search (BFS) of a binary tree. If you are unfamiliar with the algorithm for BFS, you can find detailed explanation here.

struct Node
{
  Node* left;
  Node* right;
  int value;
};

bool isBST(Node* root)
{
  if (root == NULL)
    return true;
    
  stack nodeStack;

  nodeStack.push(root);

  while (!nodeStack.empty())
  {
    Node* current = nodeStack.top();
    
    nodeStack.pop();
    
    if (current->left != NULL)
    {
      nodeStack.push(current->left);
      if (current->left->value > current->value)
        return false;
    }

    if (current->right != NULL)
    {
      nodeStack.push(current->right);
      if (current->right->value < current->value)
        return false;
    }
  }

  return true;
}

Anyway, for every node we check whether its children obey the rules of binary search tree. If the current node has a left child, the child's value must be less than the current node's value. On the other hand, if the current node has a right child, the right child's value must be greater than the current node's value. Therefore, a binary tree with all nodes that satisfy those rules is a binary tree. We return true when we check all nodes and none of them violates the rules. However, if there is any violation, we simply return false.

References

• http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/

Read More

Compute Maximum Depth or Height of binary search tree

Given a binary tree, compute its "maxDepth" -- the number of nodes along the longest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0, the maxDepth of the tree below is 3.

      1
   /    \
  2      3
 /   \   /    \
4   5  6   7


Recursive approach

/*
 Compute the "maxDepth" of a tree -- the number of nodes along
 the longest path from the root node down to the farthest leaf node.
*/
int maxDepth(struct node * node) {
    if (node == NULL) {
        return (0);
    } else {
        // compute the depth of each subtree
        int lDepth = maxDepth(node - > left);
        int rDepth = maxDepth(node - > right); // use the larger one
        if (lDepth > rDepth) return (lDepth + 1);
        else return (rDepth + 1);
    }
}

Iterative approach

We could apply the same in-order traversal of a BST in the binary tree. By saying “in-order” traversal I mean traversing the tree such that it reaches the leaf first (deepest). In other words, we are doing a Depth-first Search (DFS). In fact, all three kinds of tree traversal (pre-order, in-order, and post-order) are doing DFS. Therefore, we could modify any existing iterative solution of tree traversals to solve this problem.
As pre-order and in-order iterative traversals are easier to implement, your best bet is to code either one of them during an interview session. As we traverse the tree, we would keep track of the current depth and record each node’s depth, so that we know which depth we are in when we return to the node at a later time. (In pre-order or in-order traversals, it might return several levels above the current level when a node is popped off the stack).
On the other hand, post-order traversal guarantees to return exactly one level above a node that is popped off the stack. Therefore, we could devise a solution utilizing post-order traversal without modifying the existing tree structure. We keep track of the current depth and update the maximum depth as we traverse the tree.
Another solution is to utilize Breadth-first Search (BFS). Unlike DFS, we traverse the tree level by level, thus we are able to obtain the max depth in a direct manner. So BFS is like level order traversal and BFS is not.

Below is the code for finding the maximum depth of a binary tree using post-order traversal, without recursion.

int maxDepthIterative(BinaryTree *root) {
  if (!root) return 0;
  stack<BinaryTree*> s;
  s.push(root);
  int maxDepth = 0;
  BinaryTree *prev = NULL;
  while (!s.empty()) {
    BinaryTree *curr = s.top();
    if (!prev || prev->left == curr || prev->right == curr) {
      if (curr->left)
        s.push(curr->left);
      else if (curr->right)
        s.push(curr->right);
    } else if (curr->left == prev) {
      if (curr->right)
        s.push(curr->right);
    } else {
      s.pop();
    }
    prev = curr;
    if (s.size() > maxDepth)
      maxDepth = s.size();
  }
  return maxDepth;
}

Thanks.

Read More