Get Min from Stack

JavaView on GFG

Time: O(1)

Space: O(n)

Problem Overview

Stack that supports getMin() in O(1).

See our study guide for structured GFG and LeetCode practice.

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?