Divide and conquer

Min and Max finding

Pinterest LinkedIn Tumblr

Write a function to find minimum and maximum value from the queue. You can use two stacks to store the values. Stack uses last in first out approach to push and pop elements.

Write a program to implement a queue with two stacks for finding minimum and maximum items using (1) time?

source Code

package com.dsacode.Algorithm.divideconquer;
 
import java.util.Arrays;
import java.util.Stack;
 
public class QueueMaxMin extends Stack< Integer > {
 
      
    private static final long serialVersionUID = 1L;
    private Stack< Integer > minStack;
        private Stack< Integer > maxStack;
 
        public QueueMaxMin () {
            minStack = new Stack< Integer >();   
            maxStack = new Stack< Integer >();   
        }
 
        public void push(int value){
            if (value <= min()) {
                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();
            }
        }
      
    public void display(){
         Stack< Integer > l = new Stack< Integer >();
         l.addAll(minStack);
         l.addAll(maxStack);
            if(!l.isEmpty())
                System.out.println("Itmes in the Stack: "+Arrays.toString(l.toArray()));
 
    }
    public static void main(String[] args) {
        int[] array={12,1,56,34,78,99,11};
         QueueMaxMin obj = new QueueMaxMin();
         for(int i : array)
             obj.push(i);
          
         obj.display();
 
         System.out.println("Minimum item from the stack:" + obj.min());
          
         System.out.println("Maximum item from the stack:" + obj.max());
 
    }
 
}

Output

Items in the Stack: [12, 1, 12, 56, 78, 99]
Minimum item from the stack:1
Maximum item from the stack:99

Algorithm Explanation

Create two stack. One with minimum values and one with maximum values.
If the value is less than max stack top element, push the element into minimum stack.
If the value is more than min stack top element, push the element into maximum stack.
When the user want minimum pop the element from the minimum stack. If the user want maximum, pop the element from maximum stack.

Time Complexity

Best CaseAverage CaseWorst Case
O(1)

Reference

  1. http://algoviz.org/OpenDSA/Books/OpenDSA/html/Heaps.html
  2. https://en.wikipedia.org/wiki/Priority_queue

Write A Comment