Min Stack with Duplicate Minima Explained: Tracing push(3, 5, 2, 2)

Imagine you are building a system that tracks financial transactions or UI states, and you need a standard stack supporting push, pop, top, and a special getMin() operation in $O(1)$ time. Given our working example—a sequence of operations starting with push(3), push(5), push(2), push(2), followed by pop(), getMin(), pop(), and getMin()—you might initially think of keeping a single minVal variable alongside your main stack.

When you push(3), minVal becomes 3. When you push(5), minVal stays 3. But what happens when you push(2) twice, and then pop() once? If your single minVal variable was updated to 2 when the first 2 arrived, what should minVal become when you pop() the first 2? A naive tracker looks at the remaining stack and sees 3, 5, and 2, but it has lost the history of which 2 was removed and whether another 2 is still holding the minimum.

Scanning the entire stack on every getMin() call takes $O(n)$ time, destroying the core performance guarantee of a stack data structure. To achieve $O(1)$ minimum retrieval with duplicate values like our $2,2$ sequence, we need a smarter structure that remembers historical minimums without losing track of multiplicity.

To achieve an $O(1)$ time complexity for getMin(), we cannot afford to search through elements or recalculate running minimums during a pop operation. Instead, we can maintain a second data structure alongside our primary stack—often called the min stack or auxiliary stack. When you execute our locked example of operations starting with push(3), push(5), push(2), and push(2), the primary stack records every item in exact insertion order: $\{3,5,2,2\}$. The auxiliary stack, however, acts as a selective memory for minimum values.

Whenever a new value arrives, we compare it against the current minimum at the top of the auxiliary stack. If the incoming value is smaller than or equal to that minimum, we push it onto the auxiliary stack as well. This design ensures that the top of the auxiliary stack always holds the absolute minimum of all elements currently alive in the primary stack. When a pop() occurs on the primary stack, we check if the removed value matches the top of the auxiliary stack; if it does, we pop the auxiliary stack too. This symmetric movement keeps both structures perfectly synchronized.

To see our parallel min-stack model in action, let us trace the exact operation sequence from our locked example: push(3), push(5), push(2), push(2), pop(), getMin(), pop(), getMin().

Recall the golden rule of duplicate handling: the auxiliary min stack must record duplicate minimum values using a non-strict inequality ($\le$) rather than a strict one ($<$). Otherwise, popping the first instance of a minimum value would prematurely strip it from the min stack.

Given

- Primary stack: $[]$
- Auxiliary min stack: $[]$
- Operations: push(3), push(5), push(2), push(2), pop(), getMin(), pop(), getMin()

Steps

1. push(3): Primary stack becomes $[3]$. Min stack is empty, so we push 3. Min stack: $[3]$. Current minimum is 3.
2. push(5): Primary stack becomes $[3,5]$. Compare $5\le 3$ (False), so min stack remains $[3]$.
3. push(2): Primary stack becomes $[3,5,2]$. Compare $2\le 3$ (True), so push 2 to min stack. Min stack: $[3,2]$. Current minimum is 2.
4. push(2): Primary stack becomes $[3,5,2,2]$. Compare $2\le 2$ (True — this is the duplicate trap!), so push 2 to min stack. Min stack: $[3,2,2]$. Current minimum is still 2.
5. pop(): Remove top from primary stack (removes the second 2). Primary stack is now $[3,5,2]$. Since the popped value equals the top of the min stack ($2==2$), pop the min stack as well. Min stack becomes $[3,2]$.
6. getMin(): Inspect top of min stack, which is 2.
7. pop(): Remove next from primary stack (removes the first 2). Primary stack is now $[3,5]$. Since the popped value equals the top of the min stack ($2==2$), pop the min stack again. Min stack becomes $[3]$.
8. getMin(): Inspect top of min stack, which is now 3.

Result

The trace successfully returns 2 after the first pop and 3 after the second pop, proving that duplicate minima are preserved correctly without overhead.

Try this: Trace the stack state manually if the sequence started with push(2), push(2), push(1), pop(). What would the auxiliary min stack look like after the pop?

Now that you have traced the sequence push(3), push(5), push(2), push(2), pop(), getMin(), pop(), getMin(), let's test whether your mental model holds up against a slight variation in the duplicate handling rule.

Recall that the auxiliary stack must store every instance of a duplicate minimum (using $\le$ instead of $<$ during pushes) so that popping one duplicate does not prematurely strip away the running minimum for the remaining elements.

Imagine you execute the exact same initial setup: push(3), push(5), push(2), push(2). But suppose your auxiliary stack implementation mistakenly used strict inequality ($<$ instead of $\le$) when pushing new minimums.

Trace what the primary stack, auxiliary stack, and the result of getMin() would look like immediately after the first pop() operation under that flawed strict-inequality rule.

Now that you have traced every state of our working example—handling duplicate values like the second 2 without losing track of the first—you can lift this exact invariant design and drop it into new architectural challenges. The core pattern we built was maintaining a shadow auxiliary state that only updates when its inclusion criteria (such as $x\le \text{currentMin}$) are met. This decouples the query speed of expensive aggregates from the linear growth of the underlying dataset.

Consider how you would adapt this pattern to a Max Stack, which must support getMax() in $O(1)$ time alongside standard stack operations. The auxiliary stack logic flips immediately: you push to the max-stack whenever a new element is greater than or equal to the current maximum, and you pop from it only when the primary stack's popped element equals the current maximum.

Another direct application is avoiding redundant computation in recursive backtracking or tree traversals where you need to pass down state summaries. By embedding the shadow tracking logic directly into your wrapper class, callers interact with a simple interface while the underlying class manages historical invariant records safely.

When faced with a sliding window minimum problem (finding the minimum in every window of size $k$), you can no longer rely on a simple stack because elements leave from the bottom of the window rather than the top. However, the intuition of pairing elements with historical context—storing indices alongside values—evolves directly from the duplicate-min stack strategy you just mastered.

class MaxStack:
    def __init__(self):
        self.stack = []
        self.max_stack = []
    
    def push(self, val: int) -> None:
        # TODO: Implement push keeping max_stack synchronized
        pass
    
    def pop(self) -> int:
        # TODO: Implement pop maintaining duplicate maxima
        pass
    
    def getMax(self) -> int:
        # TODO: Return current maximum in O(1)
        pass