Min Stack

Share

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

Implement the MinStack class:

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

Example 1
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:

Contents

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.

Java
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.

Full source code on GitHub