Min Stack

Min Stack Link

Companies: Amazon, Netflix, Google, Bloomberg, Microsoft, Adobe, Oracle, Apple.

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

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• getMin() — Retrieve the minimum element in the stack.

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:

Methods pop, top and getMin operations will always be called on non-empty stacks.

Solution

The solution for this problem is a tricky one. As per the given constraints, we need to solve this problem in a constant time, so basically we can’t do any thing with the iterations here. Our main part to solve this problem in a constant time lies in a solution to find the minimum value in a stack because this is not possible if we simply implement stack and solve this.

To solve this problem we will apply two logics here:

• We will always push the second minimum number on to the stack before we push the upcoming number. This will help us to find the next minimum number in a constant time whenever we pop the top of the stack.
• If the current minimum number is the top of the stack, we will pop twice and change the current minimum number to be the last minimum number we popped.

Implementation:

Java

class MinStack {
    private Stack<Integer> stack;
    private int min;

    public MinStack() {
        stack = new Stack();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {

        if (x <= min) {
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }

    public void pop() {

        if (min == stack.pop()) {
            min = stack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }

}

Complexity Analysis:

• Time Complexity: O(1).
• Space Complexity: O(n).