2. Min Stack

Description

155. Min Stack

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

• 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() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with $O(1)$ time complexity for each function.

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:

• $-2^{31}\le \text{val}\le 2^{31}-1$
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most $3\times 10^4$ calls will be made to push, pop, top, and getMin.

---

Approach 1: Two Stacks ($O(1)$ Time, $O(N)$ Space)

Intuition

Maintain two separate stacks:

1. stack: Stores all inserted values in standard LIFO order.
2. minStack: Tracks the minimum value corresponding to each state of the stack.

When pushing a value val, push val to stack, and push Math.min(val, minStack.peek()) to minStack. This ensures the top of minStack always holds the minimum element for the current stack depth.

import java.util.Stack;
 
class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
 
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
 
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty()) {
            minStack.push(val);
        } else {
            minStack.push(Math.min(val, minStack.peek()));
        }
    }
 
    public void pop() {
        stack.pop();
        minStack.pop();
    }
 
    public int top() {
        return stack.peek();
    }
 
    public int getMin() {
        return minStack.peek();
    }
}
 

Complexity

• Time Complexity: $O(1)$ for push, pop, top, and getMin.
• Space Complexity: $O(N)$ — Requires extra memory for minStack.

---

Most Optimized Solution: Value Encoding with Single Stack ($O(1)$ Extra Space)

Intuition

To eliminate the second stack, maintain a single stack storing long values and a global variable min:

1. Pushing a new minimum (val < min): Instead of pushing val directly, push an encoded flag value: 2 * val - min. Then update min = val.
   • Because val < min, the encoded value $2\cdot \text{val}-\text{old\_min}$ will always be strictly smaller than val (the new minimum).
2. Popping (stack.peek() < min): Encountering a top value smaller than min indicates an encoded record. Restore the previous minimum using prev_min = 2 * min - stack.pop().
3. Reading Top (stack.peek() < min): If the top value is an encoded marker, the actual value pushed was min.

import java.util.Stack;
 
class MinStack {
    private Stack<Long> stack;
    private long min;
 
    public MinStack() {
        stack = new Stack<>();
    }
 
    public void push(int val) {
        long value = val;
        if (stack.isEmpty()) {
            min = value;
            stack.push(value);
        } else if (value < min) {
            // Encode value to store previous minimum state
            stack.push(2 * value - min);
            min = value;
        } else {
            stack.push(value);
        }
    }
 
    public void pop() {
        long top = stack.pop();
        if (top < min) {
            // Restore previous minimum
            min = 2 * min - top;
        }
    }
 
    public int top() {
        long top = stack.peek();
        if (top < min) {
            return (int) min;
        }
        return (int) top;
    }
 
    public int getMin() {
        return (int) min;
    }
}
 

Complexity

• Time Complexity: $O(1)$ for all operations.
• Space Complexity: $O(1)$ extra space beyond the primary stack storage.

---

Easy Memory Rule

“Two Stacks store pairs of (value, min_so_far). Single Stack encodes new minimums as 2 * val - min to restore previous minimums on pop() in $O(1)$ extra space.”

---

A single min variable works perfectly when pushing elements, but **it breaks completely when you pop()**.
When you pop the element that is currently the minimum, how do you know what the previous minimum was?

The Moment a Single min Variable Fails

Imagine you only keep a standard stack and a single variable min:

1. push(5) $\to$ Stack: [5], min = 5
2. push(3) $\to$ Stack: [5, 3], min = 3
3. push(7) $\to$ Stack: [5, 3, 7], min = 3
4. pop() $\to$ Pops 7. min is still 3. (No problem so far!)
5. pop() $\to$ Pops 3 (which was your current min)!

• Now 3 is gone from the stack.
• What is the new min for the remaining elements [5]?
  Without extra information, the only way to find out that 5 is the new minimum is to iterate through the entire stack and check every element—which takes $O(N)$ time. This violates the problem requirement that getMin() must run in $O(1)$ constant time.

Why Encoding (2 * val - min) is Necessary

To keep getMin() in $O(1)$ time without scanning the stack, you must store the history of previous minimums somewhere:

• Two Stacks Approach: Stores the history in a second stack.
• Single Stack Formula (2 * val - min): Bakes the previous minimum (${\text{min}}_{\text{old}}$) directly into the number stored on the stack.
  When you pop() an encoded element, the formula $2\cdot {\text{min}}_{\text{current}}-\text{top}$ mathematically reconstructs ${\text{min}}_{\text{old}}$ in $O(1)$ time without needing any extra space!

---

This formula works by creating a magic flag that solves two problems at once:

1. It creates a number strictly smaller than the new minimum, signaling that a minimum change happened here.
2. It mathematically encodes the previous minimum so it can be restored on pop().

Part 1: Why stack.push(2 * value - min)?

When a new element value arrives that is smaller than the current min:
$\text{value}<{\text{min}}_{\text{old}}$
If you subtract ${\text{min}}_{\text{old}}$ from both sides:
$\text{value}-{\text{min}}_{\text{old}}<0$
Add value to both sides:
$\text{value}+(\text{value}-{\text{min}}_{\text{old}})<\text{value}$
$2\cdot \text{value}-{\text{min}}_{\text{old}}<\text{value}$

Since value becomes the new minimum (${\text{min}}_{\text{new}}=\text{value}$), this proves:
$\text{Encoded Flag}<{\text{min}}_{\text{new}}$

Key Concept: The number pushed onto the stack ($2\cdot \text{value}-\text{min}$) is **always strictly smaller than the new min**. This guarantees that any stack entry smaller than min is an encoded flag, not a real raw value.

Part 2: Why if (top < min) return (int) min?

When you call top(), you check the value at the top of the stack:

1. If top >= min: The element was pushed normally (it wasn’t a new minimum), so top is the actual value.
2. If top < min: The element on top is the encoded flag ($2\cdot \text{value}-{\text{min}}_{\text{old}}$).
   Since this flag was only generated when value became the new min, the actual value pushed WAS min itself!
   Therefore, if top < min, you don’t return the dummy flag stored in the stack—you return min.

It restores the previous minimum using simple algebraic substitution.

The Algebraic Derivation

Recall what happens when you push(val) when val < min_old:

1. The top value stored in the stack was calculated as:
   $\text{top}=2\cdot \text{val}-{\text{min}}_{\text{old}}$
2. The current min variable was then updated to val:
   $\text{min}=\text{val}$
   Now, substitute val with min inside the equation for top:
   $\text{top}=2\cdot \text{min}-{\text{min}}_{\text{old}}$
   To restore the previous minimum (${\text{min}}_{\text{old}}$), simply solve for ${\text{min}}_{\text{old}}$:
   $\text{top}+{\text{min}}_{\text{old}}=2\cdot \text{min}$
   ${\text{min}}_{\text{old}}=2\cdot \text{min}-\text{top}$

Concrete Numerical Example

1. Push 5:

• Stack: [5]
• min = 5

1. Push 3 (New minimum! 3 < 5):

• Encoded Flag = $2\cdot (3)-5=6-5=1$
• Push 1 onto stack.
• Update min = 3.
• Stack: [5, 1]

3. Call top():

• Stack top is 1, min is 3.
• Check top < min ($1<3$) $\to$ True!
• This tells us 1 is just a dummy marker. The real value pushed was the minimum itself (3).
• Returns min = 3.

---

Approach

class MinStack {
 
    Stack<Integer> stack;
    Stack<Integer> minStack;
 
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
 
        val = Math.min(val, minStack.isEmpty() ? val : minStack.peek());
        minStack.push(val);
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}
 
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */