DSA 450 Notes

Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time O(1).

Implement the MinStack class:

push(x): Push element x onto stack
pop(): Remove the element on top of stack
top(): Get the top element
getMin(): Retrieve the minimum element in the stack

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   -> Returns -3
minStack.pop();
minStack.top();      -> Returns 0
minStack.getMin();   -> Returns -2

Approach 1: Using Auxiliary Stack (O(n) Space)

Intuition

Maintain two stacks: one for actual elements and another to track minimum at each level. When we push, we also push the current minimum to the min stack. When we pop, we pop from both stacks.

Algorithm

Main stack stores all elements
Min stack stores minimum value at each level
On push: push to main stack, push min(x, current_min) to min stack
On pop: pop from both stacks
getMin returns top of min stack

java

import java.util.*;

class MinStack {
    private Stack<Integer> mainStack;
    private Stack<Integer> minStack;
    
    public MinStack() {
        mainStack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int x) {
        mainStack.push(x);
        
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        } else {
            minStack.push(minStack.peek());
        }
    }
    
    public void pop() {
        if (!mainStack.isEmpty()) {
            mainStack.pop();
            minStack.pop();
        }
    }
    
    public int top() {
        return mainStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
    
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println("Min: " + minStack.getMin());  // -3
        minStack.pop();
        System.out.println("Top: " + minStack.top());     // 0
        System.out.println("Min: " + minStack.getMin());  // -2
    }
}

Complexity Analysis

Time Complexity: O(1) for all operations
Space Complexity: O(n) for the auxiliary min stack

Approach 2: O(1) Space Using Encoding (Optimal)

Intuition

Instead of using an extra stack, encode the previous minimum in the pushed value when a new minimum is found. When popping, if the value is less than current minimum, decode to get the previous minimum.

Key Formula:

When pushing a new minimum: push 2 * x - prevMin (this will be < x, serving as a flag)
When popping and value < min: previous min = 2 * min - poppedValue

Algorithm

If stack empty or x >= min: push x normally
If x < min: push 2*x - min, then update min to x
On pop: if top < min, current top is encoded, previous min = 2*min - top
On top: if top < min, return min (actual value), else return top

java

import java.util.*;

class MinStackOptimal {
    private Stack<Long> stack;
    private long minVal;
    
    public MinStackOptimal() {
        stack = new Stack<>();
        minVal = Long.MAX_VALUE;
    }
    
    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push((long) x);
            minVal = x;
        } else if (x < minVal) {
            // Push encoded value
            stack.push(2L * x - minVal);
            minVal = x;
        } else {
            stack.push((long) x);
        }
    }
    
    public void pop() {
        if (stack.isEmpty()) return;
        
        long top = stack.pop();
        
        // If top < minVal, it's encoded
        // Recover previous minimum
        if (top < minVal) {
            minVal = 2 * minVal - top;
        }
    }
    
    public int top() {
        if (stack.isEmpty()) return -1;
        
        long topVal = stack.peek();
        
        // If top < minVal, actual value is minVal
        if (topVal < minVal) {
            return (int) minVal;
        }
        return (int) topVal;
    }
    
    public int getMin() {
        return (int) minVal;
    }
    
    public static void main(String[] args) {
        MinStackOptimal minStack = new MinStackOptimal();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println("Min: " + minStack.getMin());  // -3
        minStack.pop();
        System.out.println("Top: " + minStack.top());     // 0
        System.out.println("Min: " + minStack.getMin());  // -2
        
        // Test with more values
        System.out.println("\nAdditional test:");
        MinStackOptimal ms2 = new MinStackOptimal();
        ms2.push(5);
        ms2.push(3);
        ms2.push(7);
        ms2.push(2);
        ms2.push(8);
        System.out.println("Min: " + ms2.getMin());  // 2
        ms2.pop();
        System.out.println("Min: " + ms2.getMin());  // 2
        ms2.pop();
        System.out.println("Min: " + ms2.getMin());  // 3
    }
}

Complexity Analysis

Time Complexity: O(1) for all operations
Space Complexity: O(1) extra space (only storing minVal variable)

Why the Encoding Works

Push encoding: When x < min:

We push 2*x - min which is guaranteed to be < x (since x < min implies x - min < 0)
This serves as a flag that actual value is different from stored value

Pop decoding: When popped value < min:

We stored 2*x - prevMin, and current min is x
So prevMin = 2*x - stored = 2*min - stored

Top retrieval: When top < min:

The actual value pushed was min (we updated min to x when pushing)

Key Takeaways

Two-stack approach is intuitive but uses O(n) extra space
Encoding approach achieves O(1) space by storing information in values
Use long long / Long to prevent integer overflow during encoding
The encoded value is always less than the new minimum (serves as a flag)
This is a classic interview problem testing both data structure design and math tricks
The O(1) space solution trades simplicity for space efficiency

Design a Stack that supports getMin() in O(1) time and O(1) extra space

Problem Statement

Approach 1: Using Auxiliary Stack (O(n) Space)

Intuition

Algorithm

Complexity Analysis

Approach 2: O(1) Space Using Encoding (Optimal)

Intuition

Algorithm

Complexity Analysis

Why the Encoding Works

Key Takeaways