Introduction & Problem Explanation

The Min Stack problem requires us to design a stack data structure that supports standard operations: push, pop, top, and retrieving the minimum element getMin, all in constant O(1) time.

A standard stack allows push and pop in O(1) time, but finding the minimum element usually requires traversing the entire stack, which takes O(n) time. The challenge here is to optimize the minimum element retrieval to be a constant time operation without losing stack properties.

Illustration of Min Stack design using double stacks in Java
Real-World Analogy: The Double Bookkeeping Ledger

Imagine keeping a history ledger of numbers in a stack. When you add a new number, you write it on the main page. To instantly answer "what is the smallest number currently in the pile?", you keep a second helper notepad right next to it. Whenever you add a number to the main pile, you check if it is smaller than the top number on your notepad. If it is (or if the notepad is empty), you write it on the notepad as well. If not, you write down a duplicate of the current minimum again. When you remove a number from the main pile, you tear off the top sheet of both the main pile and the notepad. The top sheet of your notepad always shows the current minimum!

The Algorithmic Approach

1. Auxiliary Min Stack Synchronization (O(1) Time, O(n) Space)

We use two standard stacks:

  • stack: Stores the actual data elements.
  • minStack: Stores the minimum elements seen so far.
When we perform a push(val):
  • We push val onto stack.
  • If minStack is empty, or val is less than or equal to the current minimum (the top of minStack), we push val onto minStack as well.
When we perform a pop():
  • We pop the top value from stack.
  • If the popped value matches the top of minStack, we pop it from minStack too.
This guarantees that the top of minStack always holds the minimum value currently in the main stack. All operations run in constant O(1) time.

Step-by-Step Execution Walkthrough

Let's trace the Min Stack operations: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin():

  1. Step 1 (Push -2):
    • Push -2 to stack: stack = [-2].
    • Since minStack is empty, push -2 to minStack: minStack = [-2].
  2. Step 2 (Push 0):
    • Push 0 to stack: stack = [-2, 0].
    • Compare 0 with top of minStack (-2). Since 0 > -2, we do not push 0 to minStack.
    • Stack states: stack = [-2, 0], minStack = [-2].
  3. Step 3 (Push -3):
    • Push -3 to stack: stack = [-2, 0, -3].
    • Compare -3 with top of minStack (-2). Since -3 <= -2, push -3 to minStack.
    • Stack states: stack = [-2, 0, -3], minStack = [-2, -3].
  4. Step 4 (GetMin):
    • We peek at the top of minStack. Returns -3. Constant time lookup!
  5. Step 5 (Pop):
    • Pop top of stack: returns -3. stack = [-2, 0].
    • Since the popped value -3 equals the top of minStack (-3), we pop from minStack as well: minStack = [-2].
  6. Step 6 (Top):
    • We peek at the top of stack. Returns 0.
  7. Step 7 (GetMin):
    • We peek at the top of minStack. Returns -2.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

  • if (minStack.isEmpty() || val <= minStack.peek()) minStack.push(val);: The conditional update that stores a new minimum threshold when pushed. Note the <= check, which is critical for handling duplicate minimums correctly.
  • if (stack.pop().equals(minStack.peek())) minStack.pop();: Keeps the helper stack synchronized with the main stack when a minimum element is popped off.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.Stack;

public class MinStack {

    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

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

    public int getMin() {
        return minStack.peek();
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        System.out.println("--- Min Stack Demonstration ---");
        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
    }
}

Conclusion

Solving the Min Stack problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.