Min Stack

Description

Design a stack data structure that supports the standard stack operations — push, pop, and top — along with one additional operation: retrieving the minimum element currently in the stack.

Specifically, implement the MinStack class with these methods:

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() — returns the top element of the stack without removing it
int getMin() — retrieves the minimum element in the stack

The challenge is that all four operations must run in O(1) constant time. A regular stack already supports push, pop, and top in O(1), but finding the minimum normally requires scanning all elements. Your task is to design a structure that tracks the minimum efficiently as elements are pushed and popped.

Examples

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() — initialize an empty stack
push(-2) — stack becomes [-2]
push(0) — stack becomes [-2, 0]
push(-3) — stack becomes [-2, 0, -3]
getMin() — returns -3 (the smallest of -2, 0, -3)
pop() — removes -3, stack becomes [-2, 0]
top() — returns 0 (the current top element)
getMin() — returns -2 (now that -3 is gone, -2 is the smallest remaining)

Example 2

Input:

["MinStack","push","push","push","getMin","pop","getMin"]
[[],[5],[3],[7],[],[],[]]

Output: [null, null, null, null, 3, null, 3]

Explanation:

Push 5, 3, 7 → stack is [5, 3, 7]
getMin() → returns 3 (smallest element)
pop() → removes 7, stack is [5, 3]
getMin() → returns 3 (3 is still in the stack, so the minimum hasn't changed even though we popped an element)

Example 3

Input:

["MinStack","push","push","getMin","pop","getMin"]
[[],[1],[1],[],[],[]]

Output: [null, null, null, 1, null, 1]

Explanation:

Push 1 twice → stack is [1, 1]
getMin() → returns 1
pop() → removes one 1, stack is [1]
getMin() → returns 1 (duplicates are handled correctly; the other 1 is still present)

Constraints

-2^31 ≤ val ≤ 2^31 - 1
Methods pop, top, and getMin will always be called on non-empty stacks
At most 3 × 10^4 calls will be made to push, pop, top, and getMin

Editorial

Brute Force

Intuition

The simplest approach is to use a regular stack (or list) for push, pop, and top — all of which are naturally O(1). For getMin(), we simply scan through every element in the stack to find the smallest one.

Think of it like a pile of books. Adding or removing from the top is easy. But finding the thinnest book? You have to look through the whole pile each time someone asks.

Step-by-Step Explanation

Let's trace through Example 1: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Step 1: Initialize an empty stack.

Step 2: push(-2) → stack = [-2]. Simple append.

Step 3: push(0) → stack = [-2, 0]. Another simple append.

Step 4: push(-3) → stack = [-2, 0, -3]. Three elements now.

Step 5: getMin() → Must scan ALL elements. Check -3 (top), then 0, then -2. The smallest is -3. Return -3. This required looking at all 3 elements.

Step 6: pop() → Remove -3 from top. Stack = [-2, 0].

Step 7: top() → Return 0 (top element) without removing.

Step 8: getMin() → Scan again. Check 0, then -2. The smallest is -2. Return -2. Even though we just asked for the min one operation ago, we must scan the whole stack again.

Brute Force — Scanning for Minimum Each Time — Watch how push and pop are instant, but getMin requires scanning every element in the stack from top to bottom.

Algorithm

Use a list (or dynamic array) to store stack elements
push(val): Append val to the end of the list → O(1)
pop(): Remove the last element → O(1)
top(): Return the last element → O(1)
getMin(): Iterate through all elements in the list, track the minimum, return it → O(n)

Code

class MinStack {
    vector<int> data;
public:
    MinStack() {}

    void push(int val) {
        data.push_back(val);
    }

    void pop() {
        data.pop_back();
    }

    int top() {
        return data.back();
    }

    int getMin() {
        int minVal = data[0];
        for (int i = 1; i < (int)data.size(); i++) {
            minVal = min(minVal, data[i]);
        }
        return minVal;
    }
};

class MinStack:
    def __init__(self):
        self.data = []

    def push(self, val: int) -> None:
        self.data.append(val)

    def pop(self) -> None:
        self.data.pop()

    def top(self) -> int:
        return self.data[-1]

    def getMin(self) -> int:
        return min(self.data)

class MinStack {
    private List<Integer> data;

    public MinStack() {
        data = new ArrayList<>();
    }

    public void push(int val) {
        data.add(val);
    }

    public void pop() {
        data.remove(data.size() - 1);
    }

    public int top() {
        return data.get(data.size() - 1);
    }

    public int getMin() {
        int minVal = data.get(0);
        for (int i = 1; i < data.size(); i++) {
            minVal = Math.min(minVal, data.get(i));
        }
        return minVal;
    }
}

Complexity Analysis

Time Complexity:

push(): O(1)
pop(): O(1)
top(): O(1)
getMin(): O(n) — must scan every element to find the minimum

With up to 3 × 10^4 calls, if half are push and half are getMin, the worst case is roughly (1.5×10^4) × (1.5×10^4) = 2.25 × 10^8 operations — too slow for strict time limits.

Space Complexity: O(n) for the stack itself (no extra space beyond the elements).

Why This Approach Is Not Efficient

The bottleneck is getMin(). Every call scans through all n elements in the stack, costing O(n) time. Since getMin() can be called up to 3 × 10^4 times, and the stack can hold up to 3 × 10^4 elements, the worst-case total work is O(n × number_of_getMin_calls) ≈ 9 × 10^8 — far too slow.

The root cause is amnesia: after computing the minimum, we immediately forget the answer. The next getMin() call starts from scratch. Even after a single push() or pop() that may not affect the minimum at all, we recompute everything.

Key insight: What if each level of the stack remembered what the minimum was at that point? When we push a new element, we can compute the new minimum in O(1) by comparing it with the previous minimum. When we pop, the previous level already knows its own minimum. This eliminates the need to scan entirely.

Better Approach - Store Minimum at Each Level

Intuition

Instead of storing just the value at each stack position, store a pair: the value itself AND the minimum of all elements from the bottom up to this level.

When we push a new value, the new minimum is simply min(new_value, previous_top_min) — a single O(1) comparison. When we pop, the minimum of the remaining stack is already stored in the new top's pair. When we call getMin(), we just read the minimum from the top pair.

Imagine a stack of sticky notes. Each note has the actual number on the front, and on the back you write 'the smallest number in the stack up to this point.' When someone asks for the minimum, you just flip the top note over — no searching needed. When you remove the top note, the note underneath already has the correct minimum for the remaining stack.

Step-by-Step Explanation

Let's trace through Example 1: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Step 1: Initialize empty pair stack.

Step 2: push(-2). Stack is empty, so -2 is both the value and the minimum. Push pair (-2, min: -2).

Step 3: push(0). Compare 0 with previous min -2: min(0, -2) = -2. The minimum doesn't change. Push pair (0, min: -2).

Step 4: push(-3). Compare -3 with previous min -2: min(-3, -2) = -3. New minimum found! Push pair (-3, min: -3).

Step 5: getMin(). Just read the min portion of the top pair → -3. O(1)! No scanning.

Step 6: pop(). Remove top pair (-3, min: -3). The new top is (0, min: -2). The correct minimum -2 is already stored there.

Step 7: top(). Read the value portion of the top pair → 0. O(1).

Step 8: getMin(). Read the min portion of the top pair → -2. Correct! The minimum was automatically 'restored' when we popped.

Pair Stack — Each Level Remembers Its Minimum — Watch how each stack entry stores both the value and the running minimum. getMin() becomes an instant O(1) peek with no scanning.

Algorithm

Use a stack where each entry is a pair: (value, current_minimum)
push(val):
- If stack is empty, push (val, val) — val is the minimum
- Otherwise, compute newMin = min(val, stack_top.min) and push (val, newMin)
pop(): Remove the top pair
top(): Return the value field of the top pair
getMin(): Return the min field of the top pair

Code

class MinStack {
    stack<pair<int, int>> st; // {value, current_min}
public:
    MinStack() {}

    void push(int val) {
        int newMin = st.empty() ? val : min(val, st.top().second);
        st.push({val, newMin});
    }

    void pop() {
        st.pop();
    }

    int top() {
        return st.top().first;
    }

    int getMin() {
        return st.top().second;
    }
};

class MinStack:
    def __init__(self):
        self.stack = []  # each entry: (value, current_min)

    def push(self, val: int) -> None:
        new_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, new_min))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

class MinStack {
    private Stack<int[]> stack; // each entry: [value, current_min]

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        int newMin = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[]{val, newMin});
    }

    public void pop() {
        stack.pop();
    }

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

    public int getMin() {
        return stack.peek()[1];
    }
}

Complexity Analysis

Time Complexity:

push(): O(1) — one comparison + one stack push
pop(): O(1) — one stack pop
top(): O(1) — read the value field
getMin(): O(1) — read the min field

All operations are constant time, which is a massive improvement over the brute force's O(n) getMin.

Space Complexity: O(n) extra

Each stack entry stores two integers instead of one, effectively doubling the memory usage. For n elements, we use 2n integers of space (n for values, n for stored minimums). With n up to 3 × 10^4, this is fine in practice, but we can ask: is it possible to achieve O(1) extra space while keeping O(1) time for all operations?

Why This Approach Is Not Efficient

The pair-stack approach achieves O(1) for all operations — a perfect time complexity. However, it uses O(n) extra space by storing the minimum alongside every single element.

Notice that the stored minimum only changes when we push a value that is smaller than the current minimum. In a stack of 1000 elements where the minimum was set by the very first push, we store the same minimum value 1000 times — enormous redundancy.

Key insight: Instead of explicitly storing the previous minimum at every level, what if we could encode the previous minimum inside the stack value itself using a mathematical trick? When the minimum changes, we push a transformed value that lets us recover the old minimum during a pop. This eliminates the need for any extra storage beyond a single variable tracking the current minimum.

Optimal Approach - Single Variable Encoding

Intuition

We maintain a single variable minVal that always holds the current minimum. The clever part is what we store in the stack when a new minimum arrives:

Push logic:

If val >= minVal, push val normally (it doesn't change the minimum).
If val < minVal, push 2 * val - minVal instead (an encoded sentinel), then update minVal = val.

Why does this work? The encoded value 2 * val - minVal is always less than val (since val < minVal implies val - minVal < 0, so 2*val - minVal = val + (val - minVal) < val). This means the encoded value is always less than minVal, which acts as a flag during pop.

Pop logic:

If the top value ≥ minVal, it's a normal value — just pop it.
If the top value < minVal, it's an encoded sentinel. The previous minimum was 2 * minVal - top, so restore minVal = 2 * minVal - top, then pop.

Top logic:

If the top value ≥ minVal, return it directly.
If the top value < minVal, the actual value stored at this position is minVal (which replaced the encoded value conceptually).

Think of it like a secret code: when a new champion (smaller value) arrives, we write a coded message on the stack that lets us reconstruct who the previous champion was if the new one leaves.

Step-by-Step Explanation

Let's trace through Example 1: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Step 1: Initialize: empty stack, minVal is undefined.

Step 2: push(-2). Stack is empty → push -2 as-is, set minVal = -2. Stack: [-2].

Step 3: push(0). Is 0 < minVal(-2)? No (0 ≥ -2). Push 0 normally. Stack: [-2, 0]. minVal stays -2.

Step 4: push(-3). Is -3 < minVal(-2)? YES! This is a new minimum.

Encode: push 2×(-3) - (-2) = -6 + 2 = -4. Stack: [-2, 0, -4].
Update: minVal = -3.
Note: -4 < -3 (encoded value is always less than the new min, acting as a flag).

Step 5: getMin(). Return minVal = -3. O(1).

Step 6: pop(). Top = -4. Is -4 < minVal(-3)? YES → encoded sentinel detected!

Restore previous min: 2×(-3) - (-4) = -6 + 4 = -2. Set minVal = -2.
Pop -4 from stack. Stack: [-2, 0].

Step 7: top(). Top = 0. Is 0 ≥ minVal(-2)? Yes → 0 is the actual value. Return 0.

Step 8: getMin(). Return minVal = -2. The old minimum was correctly restored from the encoding.

Single Variable Encoding — O(1) Space Min Tracking — Watch how encoded sentinel values replace the auxiliary stack. When the minimum changes, we push a mathematical code that encodes the previous minimum, recoverable during pop.

Algorithm

Maintain a stack and a variable minVal
push(val):
- If stack is empty: push val, set minVal = val
- If val < minVal: push 2 * val - minVal, update minVal = val
- Otherwise: push val normally
pop():
- Let top = stack.top(), pop it
- If top < minVal: this was encoded → restore minVal = 2 * minVal - top
top():
- If stack.top() < minVal: return minVal (the encoded value hides the actual val, which equals minVal)
- Otherwise: return stack.top()
getMin(): return minVal

Important: Use long long (C++) / long (Java) for stack elements to avoid integer overflow with the 2 * val - minVal computation when val is near INT_MIN.

Code

class MinStack {
    stack<long long> st;
    long long minVal;
public:
    MinStack() : minVal(0) {}

    void push(int val) {
        if (st.empty()) {
            st.push(val);
            minVal = val;
        } else if (val < minVal) {
            st.push(2LL * val - minVal); // encoded sentinel
            minVal = val;
        } else {
            st.push(val);
        }
    }

    void pop() {
        long long top = st.top();
        st.pop();
        if (top < minVal) {
            // top was encoded; restore previous min
            minVal = 2 * minVal - top;
        }
    }

    int top() {
        long long t = st.top();
        // if encoded, actual value is minVal
        return (t < minVal) ? (int)minVal : (int)t;
    }

    int getMin() {
        return (int)minVal;
    }
};

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_val = 0

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(val)
            self.min_val = val
        elif val < self.min_val:
            self.stack.append(2 * val - self.min_val)  # encoded
            self.min_val = val
        else:
            self.stack.append(val)

    def pop(self) -> None:
        top = self.stack.pop()
        if top < self.min_val:
            # top was encoded; restore previous min
            self.min_val = 2 * self.min_val - top

    def top(self) -> int:
        t = self.stack[-1]
        return self.min_val if t < self.min_val else t

    def getMin(self) -> int:
        return self.min_val

class MinStack {
    private Stack<Long> stack;
    private long minVal;

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push((long) val);
            minVal = val;
        } else if (val < minVal) {
            stack.push(2L * val - minVal); // encoded sentinel
            minVal = val;
        } else {
            stack.push((long) val);
        }
    }

    public void pop() {
        long top = stack.pop();
        if (top < minVal) {
            minVal = 2 * minVal - top; // restore previous min
        }
    }

    public int top() {
        long t = stack.peek();
        return (t < minVal) ? (int) minVal : (int) t;
    }

    public int getMin() {
        return (int) minVal;
    }
}

Complexity Analysis

Time Complexity:

push(): O(1) — one comparison, one arithmetic operation, one stack push
pop(): O(1) — one comparison, one arithmetic operation, one stack pop
top(): O(1) — one comparison, one stack peek
getMin(): O(1) — return a single variable

All four operations run in constant time, matching the pair-stack approach.

Space Complexity: O(1) extra

We use only a single additional variable (minVal) beyond the stack itself. The stack stores exactly n elements (one per push), with no pairs or auxiliary structures. This is a strict improvement over the O(n) extra space of the pair-stack approach.

Caveat: The 2 * val - minVal computation can overflow 32-bit integers when val is near -2^31. We use long long / long to handle this safely. This is a minor implementation detail, not a complexity concern.

Language Essentials & Syntax

EASY

Pattern-Based Logic Building

EASY

Standard Libraries & Collections

EASY

Essential Mathematics

EASY

MEDIUM

Recursion Fundamentals

EASY

Hashing Essentials

EASY

MEDIUM

Comparison-Based Sorts

EASY

Divide & Conquer Sorts

EASY

MEDIUM

Array Fundamentals

EASY

MEDIUM

Intermediate Array Problems

EASY

MEDIUM

Advanced Array Challenges

EASY

MEDIUM

HARD

Searching in Sorted Arrays

EASY

MEDIUM

Search Space Reduction

EASY

MEDIUM

HARD

Matrix Binary Search

EASY

MEDIUM

HARD

Core String Operations

EASY

MEDIUM

Intermediate String Challenges

EASY

MEDIUM

Singly Linked List Basics

EASY

MEDIUM

Doubly Linked List Basics

EASY

MEDIUM

Linked List Techniques

EASY

MEDIUM

Doubly Linked List Techniques

MEDIUM

HARD

Advanced Linked List Challenges

MEDIUM

HARD

Building Recursive Thinking

EASY

MEDIUM

Generating Subsequences

EASY

MEDIUM

Exhaustive Search & Constraint Solving

MEDIUM

HARD

Bitwise Operations Fundamentals

EASY

MEDIUM

Bit Manipulation Applications

EASY

MEDIUM

Number Theory & Primes

EASY

MEDIUM

HARD