Design a stack which returns the minimum element in constant time O(1)

Problem statement : Design and implement a stack which returns the minimum element of the stack in constant time. The implementation should support other stack operations push(), pop(), peek(), getSize(), isEmpty(), isFull() in constant time with no degrade in performance and a getMin() method which returns the minimum element with O(1) time complexity.

Prerequisites :

Knowledge of Java, Data structures, Stack data structure and operations performed on it. Understanding of time and space complexity is required.

Our first thought :

The first solution that would come to our mind is to maintain a variable which will hold the minimum value of the stack every time we push a new element to the stack. For example, when the stack is empty initially, the minimum element would be the first element pushed to the stack. The second time push operation is made, we make a comparison of the minimum element and the new element to be pushed. If the new element is greater than the minimum element then we just push the new element to the stack and keep the minimum element as it is. If the new element is smaller than the minimum element, then we assign the value of new element to the minimum element and push the new element to the stack.

Problem with the above approach arises when pop operation is performed. Popping an element from the top of the stack which is not equal to the minimum element works fine, because we still have the track of the minimum element of the stack in the variable maintained. But if the element popped is equal to the minimum element, then the value stored in the minimum element variable is no longer the minimum element of the stack. Hence, how do we find the minimum element after this pop operation is performed? In other words how do we find the previous minimum element of the stack?

Solution using two stacks :

To solve the above problem we use two stacks, one for storing the actual elements and the other for storing the minimum element every time we push a new element to the stack.

Algorithm :

1. Declare a stack mainStack of type Stack<Integer> for storing the actual elements.
2. Declare a stack minStack of type Stack<Integer> for storing the minimum element each time an element is pushed to the mainStack.
3. To push an element x, check if the element is less than the topmost element of minStack. If it is, then push the element to both mainStack and minStack. Else re-push the topmost element of minStack to minStack and push x to mainStack.
4. To pop an element, pop from the mainStack as well as minStack.
5. Minimum element at any point in time is the topmost element of the minStack.

Diagrammatic representation :

Implementation :

import java.util.Stack;

class MinElementUsing2Stacks {

	Stack<Integer> mainStack;
	Stack<Integer> minStack;

	MinElementUsing2Stacks() {
		mainStack = new Stack<Integer>();
		minStack = new Stack<Integer>();
	}

	/*
	 * Method which pushes an element to the main stack and pushes to the min
	 * stack only if the data to be pushed is less than the top most element of
	 * min stack, else pushes the min element again to minStack
	 */
	void push(int data) {
		mainStack.push(data);

		// check if the minStack is empty
		if (minStack.empty()) {
			minStack.push(data);

		} else {
			int min = minStack.peek();
			minStack.push(data < min ? data : min);

		}
	}

	/*
	 * Method which pops an element from main stack and min stack
	 * 
	 */
	int pop() {
		if (isEmpty()) {
			System.out.println("Stack is empty, cannot pop elements.");
			return -1;
		} else {
			minStack.pop();
			return mainStack.pop();
		}
	}

	// method which checks if the main stack is empty
	boolean isEmpty() {
		return mainStack.empty();
	}

	// method which peeks the topmost element of main stack
	int peek() {
		return mainStack.peek();
	}

	// method which returns the size of the main stack
	int getSize() {
		return mainStack.size();
	}

	// method which returns the minimum element
	int getMin() {
		if (minStack.empty()) {
			System.out.println("Min stack is empty");
			return -1;
		} else {
			return minStack.peek();
		}
	}

}

public class MinElementUsing2StacksMain {

	public static void main(String[] args) {

		MinElementUsing2Stacks s = new MinElementUsing2Stacks();

		s.push(2); //push 2
		s.push(2); //push 2
		s.push(1); //push 1
		s.push(4); //push 4
		s.push(5); //push 5
		s.push(5); //push 5
		System.out.println(s.getMin()); //prints 1
		s.pop(); //pops 5 from mainStack and 1 from minStack
		s.pop(); //pops 5 from mainStack and 1 from minStack
		System.out.println(s.getMin()); // prints 1
		s.pop(); //pops 4 from mainStack and 1 from minStack
		s.pop(); //pops 1 from mainStack and 1 from minStack
		s.pop(); //pops 2 from mainStack and 2 from minStack
		System.out.println(s.getMin()); //prints 2
	}

}

Output of above code:

1
1
2

Time and space complexity of above implementation :

All operations push(), pop(), peek(), isEmpty(), getSize() and getMin() have constant time complexity i.e. O(1) as the time required to perform these operations individually does not change with the size of the input. The above approach requires ‘n’ elements extra space for the auxiliary stack used to store minimum elements. Hence the space complexity is O(n).

Here is the link to the code on my github profile, Minimum element using 2 stacks.

Thank you for reading. You can share your feedback on below comments section.