Get Min from Stack

JavaView on GFG

Time: O(1)

Space: O(n)

Intuition

Stack that supports getMin() in O(1). Maintain auxiliary min stack.

Algorithm

1Push: push to main stack; push min(val, minStack.top()) to minStack.
2Pop: pop both stacks. GetMin: return minStack.top().

Common Pitfalls

•Same as LC 155. Min stack always has current minimum at top. Both stacks stay in sync.

Get Min from Stack.java

Java

// Approach: Auxiliary stack tracking minimums. Push to aux only when new element <= current min.
// Time: O(1) Space: O(n)
class Solution {
    Stack<Integer> st;
    Stack<Integer> minSt;

    public Solution() {
        st = new Stack<>();
        minSt = new Stack<>();
    }

    // Add an element to the top of Stack
    public void push(int x) {
        st.push(x);

        if (minSt.isEmpty() || minSt.peek() >= x)
            minSt.push(x);
    }

    // Remove the top element from the Stack
    public void pop() {
        if (st.isEmpty())
            return;

        int x = st.pop();

        if (minSt.peek() == x)
            minSt.pop();
    }

    // Returns top element of the Stack
    public int peek() {
        if (st.isEmpty())
            return -1;

        return st.peek();
    }

    // Finds minimum element of Stack
    public int getMin() {
        if (minSt.isEmpty())
            return -1;

        return minSt.peek();
    }
}

Was this solution helpful?