Pseudo-code:

text
class MinStack:
    list data

    push(val):
        data.add(val)

    pop():
        data.removeLast()

    getMin():
        min_val = infinity
        for x in data:
            min_val = min(min_val, x)
        return min_val

Complexity Analysis:

• Push/Pop/Top: $O(1)$
• GetMin: $O(N)$, where $N$ is the number of elements in the stack.

Why it fails: While this approach is correct in terms of logic, it fails the strict performance constraints. The problem explicitly mandates $O(1)$ time complexity for getMin. If the stack contains thousands of elements, iterating through them is inefficient and will likely lead to a Time Limit Exceeded (TLE) result on large test cases.

Core Insight for Min Stack

The key intuition for the LeetCode 155 solution lies in the observation that the minimum element of a stack changes in a predictable way. The minimum value only changes when a new smaller element is added or when the current minimum element is removed.

Because a stack enforces a strict LIFO order, the state of the stack at any given height is immutable once elements are pushed above it. This means that for every element currently in the stack, the "minimum value of the stack at the moment this element was the top" is a fixed historical fact.

We can maintain this history using an auxiliary stack (often called the minStack). This secondary stack tracks the minimum value seen so far as the main stack grows.

Visual Description: Visualize two vertical columns representing stacks. The left column (Main Stack) holds the actual data values $[-2, 0, -3]$. The right column (Min Stack) holds the minimum values corresponding to the state of the main stack $[-2, -2, -3]$.

• When $-2$ is pushed, the current min is $-2$.
• When $0$ is pushed, the min is still $-2$.
• When $-3$ is pushed, the min updates to $-3$. When we pop $-3$ from the Main Stack, we also pop the corresponding state from the Min Stack, instantly reverting the "current minimum" to $-2$.

Execution Flow

Let's trace the algorithm with the input: push(-2), push(0), push(-3), getMin(), pop().

1. Initialize: mainStack = [], minStack = [].
2. push(-2):
   • Push -2 to mainStack. mainStack is [-2].
   • minStack is empty, so push -2. minStack is [-2].
3. push(0):
   • Push 0 to mainStack. mainStack is [-2, 0].
   • Compare 0 with minStack.top() (which is -2). 0 > -2, so do NOT push to minStack. minStack remains [-2].
4. push(-3):
   • Push -3 to mainStack. mainStack is [-2, 0, -3].
   • Compare -3 with minStack.top() (-2). -3 < -2, so push -3 to minStack. minStack is [-2, -3].
5. getMin():
   • Return minStack.top(), which is -3.
6. pop():
   • Pop from mainStack. Removed value is -3. mainStack becomes [-2, 0].
   • Check if removed value (-3) equals minStack.top() (-3). Yes.
   • Pop from minStack. minStack becomes [-2].
   • The new minimum is automatically restored to -2.

Proof of Correctness

The correctness relies on the invariant that minStack.top() is always the minimum value among all elements currently in mainStack.

• Base Case: When both stacks have 1 element, minStack holds that element, which is trivially the minimum.
• Inductive Step (Push): If we push a value $X$, and $X$ is smaller than the current minimum, $X$ becomes the new minimum and is pushed to minStack. If $X$ is larger, the minimum remains unchanged, and we do not alter the top of minStack.
• Inductive Step (Pop): If we pop a value $Y$ that is not the current minimum, the minimum remains unchanged. If we pop the current minimum, we remove it from minStack, reverting the state to the previous minimum (which was valid before the current minimum was pushed).

Thus, the invariant holds for all operations.

Reference Implementation

C++ Solution for LeetCode 155

cpp
#include <stack>
#include <algorithm>

class MinStack {
private:
    std::stack<int> mainStack;
    std::stack<int> minStack;

public:
    MinStack() {
        // Initialization handled by stack constructors
    }
    
    void push(int val) {
        mainStack.push(val);
        // Push to minStack if it's empty or val is simpler/equal to current min
        if (minStack.empty() || val <= minStack.top()) {
            minStack.push(val);
        }
    }
    
    void pop() {
        if (mainStack.empty()) return;
        
        int topVal = mainStack.top();
        mainStack.pop();
        
        // If we popped the minimum, remove it from minStack too
        if (topVal == minStack.top()) {
            minStack.pop();
        }
    }
    
    int top() {
        return mainStack.top();
    }
    
    int getMin() {
        return minStack.top();
    }
};

Java Solution for LeetCode 155

java
import java.util.Stack;

class MinStack {
    private Stack<Integer> mainStack;
    private Stack<Integer> minStack;

    public MinStack() {
        mainStack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        mainStack.push(val);
        // Push to minStack if empty or val is <= current min
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public void pop() {
        // Use equals() for Integer objects, not ==
        if (mainStack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        mainStack.pop();
    }
    
    public int top() {
        return mainStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

Python Solution for LeetCode 155

python
class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        # Push to min_stack if empty or val is <= current min
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.stack:
            val = self.stack.pop()
            # If we popped the minimum, update min_stack
            if val == self.min_stack[-1]:
                self.min_stack.pop()

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

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

Why is my Java solution failing specifically on pop?

• Mistake: Comparing Integer objects using == instead of .equals().
• Reasoning: In Java, == compares object references. For numbers outside the cached range (-128 to 127), two Integer objects with the same value will have different references.
• Consequence: The logic fails to detect when the minimum element is being popped, causing minStack to desynchronize.

Why is the minimum value incorrect after popping?

• Mistake: Forgetting to push duplicate minimums onto minStack.
• Reasoning: If you push 2 then 2 again, and only store one 2 in minStack, popping one 2 from mainStack will remove the only 2 from minStack. The next getMin will return the value below it (e.g., 5), which is incorrect because a 2 still remains in mainStack.
• Consequence: Correctness failure. You must push val to minStack if val <= minStack.top(), not just val < minStack.top().