Stack - Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]
Explanation:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

Constraints:

-2³¹ <= val <= 2³¹ -1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10⁴ calls will be made to push, pop, top, and getMin

Solution 1 - Implementation of Min Stack using two stacks

In this approach, we are going to implement a min stack using two stacks, in one stack we wil maintain the stack elements that supports standard operations such as push, pop, peek and isEmpty, and in the other stack we will maintain a running minimum at each number that we add or remove. When the getMin() operation is called we will return the top element from this other stack.

import java.util.Stack; public class MinStack { final Stack<Integer> stack; final Stack<Integer> minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int val) { stack.push(val); minStack.push(minStack.isEmpty() ? val: Integer.min(val, minStack.peek())); } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } public static void main(String[] args) { MinStack minStack1 = new MinStack(); minStack1.push(-2); minStack1.push(0); minStack1.push(-3); System.out.println("Min : "+minStack1.getMin()); minStack1.pop(); System.out.println("Top : "+minStack1.top()); System.out.println("Min : "+minStack1.getMin()); } }

Complexity Analysis:

Time complexity: All the above operations runs in O(1) time.
Space complexity: O(n) for storing stack elements as well as the second stack that we are using to maintain running minimum.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis: