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 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