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

This post provides minimum element of the stack implementation in constant time O(1) and O(n) space. I have already discussed how to find minimum element of the stack using two stacks. This approach is an optimized version in which no auxiliary stack is used.

Prerequisites :

Knowledge of Java, stack data structure and understanding of time and space complexity is required.

Check previously discussed post Minimum element in constant time O(1) using auxiliary space here.

Explanation :

The logic used to find the minimum element of the stack using only one stack is “Every element has a minimum element stored up to that point in the stack”.

Algorithm :

1. Create a stack of type Stack<int[]>, where every item stored is an array consisting two values i.e. Current element and minimum element up to that point in the stack.
2. To push a new element into the stack, check if the stack is empty. If it is empty then, push the item as an array of the new element and the new element as the minimum element itself. If the stack is not empty, then compare the new element with stack top’s minimum element. Push the new item to the stack as an array of new element and the minimum of the new element and stack top minimum element.
3. To pop and item directly pop the top element of the stack.
4. To get the minimum element at any point of time, peek the stack top’s minimum element.

Diagrammatic representation :

Code implementation :

import java.util.Stack;

public class MinElementUsing1Stack {

	Stack<int[]> stack;

	// data structure initialization
	MinElementUsing1Stack() {
		stack = new Stack<int[]>();

	}

	// method to push a new element along with the min value till that point
	void push(int val) {
		// if the stack is empty push the element to stack, min=element itself
		if (stack.empty()) {
			stack.push(new int[] { val, val });
			return;
		}

		// compare the top min element with the new element, if new element is
		// smaller then add the new min as the current element
		int currentMin = stack.peek()[1];
		stack.push(new int[] { val, Math.min(currentMin, val) });

	}

	// method to pop an element from stack
	void pop() {
		stack.pop();
	}

	// method which returns min value
	int getMin() {
		return stack.peek()[1];
	}

	// method to get top element of stack
	int top() {
		return stack.peek()[0];
	}

	public static void main(String[] args) {
		MinElementUsing1Stack s = new MinElementUsing1Stack();
		s.push(5);
		System.out.println("Min element is = " + s.getMin());
		s.push(2);
		System.out.println("Min element is = " + s.getMin());
		s.push(10);
		s.push(1);
		s.push(3);

		System.out.println("Min element is = " + s.getMin());
		System.out.println("Top element is = " + s.top());

		s.pop();
		System.out.println("Min element is = " + s.getMin());
		s.pop();
		System.out.println("Min element is = " + s.getMin());

	}

}

Code output :

Min element is = 5
Min element is = 2
Min element is = 1
Top element is = 3
Min element is = 1
Min element is = 2

Time and space complexity :

Time complexity of the above methods push(), pop(), peek(), getMin() and top() are all O(1). Since we do not iterate over any elements to perform these operations.

Space complexity = O(n) since we use a stack to store ‘n’ elements. We do not use any auxiliary stack to find the minimum element of the stack.

Link to the above code on my github profile, Minimum element using one stack.

Thank you so much for reading. Your feedback is highly appreciated..!!