Implementing the Stack

This module explores the core principles of Stack Operations and the Min Stack problem, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Problem Definition

A Stack is an Abstract Data Type (ADT) that follows LIFO (Last In, First Out). Core operations must be O(1):

• Push(val): Add val to the top.
• Pop(): Remove and return the top element.
• Peek(): Return the top element without removing it.

Challenge (Min Stack): Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Examples

Example 1:

Input:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output:
[null,null,null,null,-3,null,0,-2]

Constraints

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

Edge Cases & Clarifying Questions

• What if multiple elements have the same minimum value? The stack should maintain duplicates correctly so that popping one does not lose the minimum.
• Are we constrained on space? O(N) space is generally acceptable for this problem to achieve O(1) time.
• What if we pop an empty stack? Per the constraints, this will not happen.

---

2. Interactive Analysis

Push values and watch how the MinStack updates. Note that MinStack only records values smaller than or equal to the current minimum.

Main Stack

Min Stack

Current Min: None

---

3. Intuition (The “Genesis”)

Pattern Name: Auxiliary Data Structure (Two Stacks)

Brute Force Approach: The most straightforward approach is to maintain a standard stack. For push, pop, and top, operations are inherently O(1). However, to find the minimum element (getMin), we would need to iterate through all elements currently in the stack, taking O(N) time. This violates the problem requirement of constant time retrieval.

Optimized Approach: We need to “cache” the minimums to retrieve them in O(1) time. Imagine a stack of plates. On each plate, we write a number. On a sticky note attached to that plate, we write “The smallest number from this plate downwards”. When we remove a plate, we remove its sticky note too. The new top plate reveals the previous minimum.

We implement this “sticky note” concept using a second stack, minStack.

Common Pitfalls

• Forgetting to push duplicate minimums: If the current value equals the current minimum, it must be pushed onto the minStack. If you only push strictly smaller values, you will incorrectly remove the minimum from the minStack when duplicates exist.
• Using == for object comparison: In languages like Java, if you store wrapper classes (like Integer) in the stack instead of primitives, comparing val == minStack.peek() will compare memory references. Always use .equals() for objects or rely on primitives/unboxing.

---

4. Implementation

Java

// Note: Use Deque/ArrayDeque, NOT Stack (legacy)
class MinStack {
  private Deque<Integer> stack = new ArrayDeque<>();
  private Deque<Integer> minStack = new ArrayDeque<>();

  public void push(int val) {
    stack.push(val);
    // Only push to minStack if new value is <= current min
    if (minStack.isEmpty() || val <= minStack.peek()) {
      minStack.push(val);
    }
  }

  public void pop() {
    int val = stack.pop();
    // Only pop minStack if we removed the min value
    // Use .equals() because we are comparing Objects (Integer)
    if (minStack.peek().equals(val)) {
      minStack.pop();
    }
  }

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

Go

type MinStack struct {
  stack    []int
  minStack []int
}

func (this *MinStack) Push(val int) {
  this.stack = append(this.stack, val)
  // Push to minStack if empty or smaller/equal
  if len(this.minStack) == 0 || val <= this.minStack[len(this.minStack)-1] {
    this.minStack = append(this.minStack, val)
  }
}

func (this *MinStack) Pop() {
  val := this.stack[len(this.stack)-1]
  this.stack = this.stack[:len(this.stack)-1]
  // Pop from minStack if values match
  if val == this.minStack[len(this.minStack)-1] {
    this.minStack = this.minStack[:len(this.minStack)-1]
  }
}

func (this *MinStack) GetMin() int {
  return this.minStack[len(this.minStack)-1]
}

---

5. Complexity Analysis

Strategy	Time	Space	Notes
Two Stacks	O(1)	O(N)	Every operation is constant time. Space stores redundant mins.