Design a stack that supports getMinimum() in O(1) time

Problem statement:

Find the minimum element in a stack in O(1) time complexity and O(n) space complexity

Solution:

Maintain another stack and keep pushing the minimum element on the stack as in when found.

Before each push on stack 1, just check if the current element is less than the top element of the second stack if yes then push it on to stack 2.

While popping an element from stack1 check if the top of stack2 is same as the element in that case pop both the elements so that next minimum would show up on stack 2 for next min operation.

Inserts an element e1 to Stack.

push(int e1)

1) push e1 to the stack 1.

2) compare e1 with the top element(=e2) of the stack 2 (the auxiliary stack).

   a) If e1<e2, then push e1 to the auxiliary stack.

   b) If e1>e2, then push e2 to the auxiliary stack.

Removes an element from Stack and return the removed element.

int pop()

1) pop the top element from the auxiliary stack.

2) pop the top element from the actual stack and return it.

The step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.

Returns the minimum element from Stack.

int getMinimum()

1) Return the top element of the auxiliary stack.

import java.util.Stack;

class MyStack {

     Stack<Integer> stack1;

     Stack<Integer> stack2;

     /** MyStack constructor. */

     private MyStack() {

           this.stack1 = newStack<Integer>();

           this.stack2 = newStack<Integer>();

     }

     /** Return the instance of the stack. */

     public static MyStack getMyStackInstance() {

           return newMyStack();

     }

    

     /** Insert the element into the stack. */

     public intinsert(int number) {

           int result = stack1.push(number);

           if(stack2.isEmpty() || stack2.peek()>number) {

                stack2.push(number);

           } else {

                int peek = stack2.peek();

                stack2.push(peek);

           }

           return result;

     }

     /** Delete the Top from the stack. */

     public boolean delete() {

           boolean result = false;

           if(!stack1.isEmpty()) {

                stack1.pop();

                stack2.pop();

           }

           return result;

     }

     /** Return the minimum element in the stack. */

     public intgetMinimum() {

           int result = -1;

           if(!stack2.isEmpty()) {

                result = stack2.peek();

           }

           return result;

     }

}

public class StackOperations {

     /** Driver method. */

     public static void main(String[] args) {

           MyStack myStack = MyStack.getMyStackInstance();

           int number = 10;          

           myStack.insert(number);

           int min = myStack.getMinimum();

           System.out.println("Minimum : "+min);

          

           number = 8;

           myStack.insert(number);

           min = myStack.getMinimum();

           System.out.println("Minimum : "+min);

          

           number = 7;         

           myStack.insert(number);

           min = myStack.getMinimum();

           System.out.println("Minimum : "+min);

          

           number = 14;        

           myStack.insert(number);

           min = myStack.getMinimum();

           System.out.println("Minimum : "+min);

          

           number = 6;         

           myStack.insert(number);

           min = myStack.getMinimum();

           System.out.println("Minimum : "+min);

           myStack.delete();

           min = myStack.getMinimum();

           System.out.println("Minimumag after delete : "+min);

          

           myStack.delete();

           min = myStack.getMinimum();

           System.out.println("Minimumag after delete : "+min);

          

          

           myStack.delete();

           min = myStack.getMinimum();

           System.out.println("Minimumag after delete : "+min);

     }

} 

This would ensure that we pop out the minimum element in O(1) time.