LeetCode 155: Min Stack in C++ Using State Tracking

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original LeetCode page.

Article Summary

The Min Stack problem asks us to design a stack that supports the standard push, pop, and top operations while also returning the minimum element in constant time.

A normal stack already performs push, pop, and top in O(1) time. The main challenge is implementing getMin() without searching through every element in the stack.

The key idea is to treat every push operation as the creation of a new stack state. Along with each value, we store the minimum value for that state. When an element is removed, the previous minimum is automatically restored because it was saved in the pair below it.

This article explains how to recognize the stack pattern, why a single minimum variable is insufficient, and how storing the current minimum with every value allows all four operations to run in O(1) time.

Original Problem and Credit

This article is based on the LeetCode problem “155. Min Stack.”

• Original problem: https://leetcode.com/problems/min-stack/description/
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

The original problem statement is summarized and adapted rather than reproduced in full.

Real-World Scenario

Imagine a hypothetical cloud deployment platform that maintains a history of deployment performance scores.

A lower score represents better performance.

The platform must support four operations:

• Record a new deployment score.
• Roll back the most recent deployment.
• Retrieve the current deployment score.
• Retrieve the best, or minimum, score among all active deployments.

Deployments follow a Last-In, First-Out rollback order. The most recently recorded deployment is always the first one removed.

The platform must also return the best active performance score immediately. It cannot scan the complete deployment history every time that value is requested.

Suppose the following scores are recorded:

1, 2, 0

The best active score is:

0

After the most recent deployment is rolled back, the remaining scores are:

1, 2

The best score must return to:

1

The important observation is that rolling back a deployment also rolls the minimum score back to its previous state.

This scenario is hypothetical, but it preserves the stack behavior, operation requirements, expected outputs, and constant-time restriction of the original problem.

Examples

Example 1

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

Output:
[null, null, null, null, 0, null, 2, 1]

Explanation

MinStack minStack;

minStack.push(1);
minStack.push(2);
minStack.push(0);

minStack.getMin();  // Returns 0

minStack.pop();

minStack.top();     // Returns 2
minStack.getMin();  // Returns 1

After pushing 1, 2, and 0, the minimum value is 0.

When 0 is removed, the stack returns to its previous state. In that state, the minimum value was 1.

Duplicate Minimum Example

Operations:
push(3)
push(1)
push(1)
getMin()
pop()
getMin()

Results:
getMin() returns 1
getMin() returns 1

Removing one copy of the minimum must not change the minimum when another copy remains in the stack.

Constraints

-2^31 <= val <= 2^31 - 1

The following operations are called only when the stack is nonempty:

pop
top
getMin

Every operation must run in:

O(1)

Mapping to the Original Problem

The terminology changes, but the operations and expected behavior remain mathematically equivalent.

Solution Intuition

Recognizing the Stack Pattern

The problem requires elements to be removed in the reverse order from which they were added.

Suppose the values are added in this order:

1
2
0

The removal order must be:

0
2
1

This is a Last-In, First-Out, or LIFO, pattern.

A stack is designed for this behavior:

• push adds an element to the top.
• pop removes the top element.
• top retrieves the top element.

A standard stack already supports these operations in O(1) time.

The difficulty comes from the additional getMin() operation.

Why Scanning the Stack Does Not Work

One possible approach is to search the entire stack whenever getMin() is called.

For example, suppose the stack contains:

5, 3, 7, 2, 6

We could inspect every value and determine that 2 is the minimum.

However, this requires O(n) time, where n is the number of elements in the stack.

The problem requires getMin() to run in:

O(1)

Therefore, the minimum must already be available when getMin() is called.

Why One Minimum Variable Is Not Enough

Another initial idea is to store one class variable:

int currentMinimum;

Whenever a value is pushed, we update it:

currentMinimum = std::min(currentMinimum, val);

This works while values are only being added.

The problem appears when the current minimum is removed.

Consider:

push(5)
push(2)
push(4)

The current minimum is:

2

Now remove 4:

pop()

The minimum remains 2.

Next, remove 2:

pop()

The remaining stack contains:

5

The minimum must return to 5.

However, a single variable remembers only the current minimum. It does not remember the minimum that existed before 2 was pushed.

Finding that previous minimum would require scanning the remaining stack, resulting in O(n) time.

Treating Every Push as a New State

Every push operation creates a new state of the stack.

Every pop operation restores the previous state.

Instead of storing only the current minimum, we can store the minimum associated with every stack state.

Each stack entry stores a pair:

(actual value, minimum at this state)

For example, pushing 1, 2, and 0 creates the following stack:

Top    (0, 0)
       (2, 1)
Bottom (1, 1)

The first number is the actual value.

The second number is the minimum value among that entry and every entry below it.

The top pair therefore always contains both:

• The current top value
• The current minimum value

When the top pair is removed, the pair below it already contains the correct minimum for the restored state.

Calculating the Minimum During Push

When the stack is empty, the new value is automatically the minimum:

(value, value)

For example:

push(5)

stores:

(5, 5)

When the stack is not empty, the new minimum is:

min(new value, previous minimum)

The previous minimum is stored in the second field of the current top pair.

Suppose the current top pair is:

(5, 3)

This means the current top value is 5, while the minimum of the complete stack is 3.

If we push 2, the new pair is:

(2, min(2, 3))

which becomes:

(2, 2)

If we instead push 7, the new pair is:

(7, min(7, 3))

which becomes:

(7, 3)

Why Duplicate Minimums Work

Consider:

push(3)
push(1)
push(1)

The stored pairs are:

Top    (1, 1)
       (1, 1)
Bottom (3, 3)

After removing the top pair, the next pair still records a minimum of 1.

Therefore, duplicate minimum values require no special handling.

Algorithm

1. Create a stack of integer pairs.
2. In each pair:
   • The first value stores the actual stack value.
   • The second value stores the minimum value for that stack state.
3. For push(val):
   1. If the stack is empty, push (val, val).
   2. Otherwise, read the previous minimum from the second field of the top pair.
   3. Calculate the new minimum as min(val, previous minimum).
   4. Push (val, new minimum).
4. For pop():
   • Remove the top pair.
5. For top():
   • Return the first field of the top pair.
6. For getMin():
   • Return the second field of the top pair.

Why the Algorithm Works

The main invariant is:

For every pair in the stack, the second value equals the minimum of the actual value in that pair and all actual values below it.

Base Case

When the first value is pushed, it is the only element in the stack.

The algorithm stores:

(val, val)

Because the stack contains only val, its minimum is also val.

Therefore, the invariant is true after the first push.

Push Operation

Assume the invariant is true before a new value is pushed.

The second value of the current top pair contains the minimum of the entire existing stack.

The algorithm calculates:

new minimum = min(new value, previous minimum)

This result is the minimum of:

• The new value
• Every existing value in the stack

The algorithm stores that result in the second field of the new pair.

Therefore, the invariant remains true after a push.

Pop Operation

Each pair contains the minimum for the stack state ending at that pair.

When the top pair is removed, the pair below it becomes the new top.

Its second field already contains the minimum for the restored stack state.

Therefore, no recalculation is necessary, and the invariant remains true after a pop.

Top Operation

The first field of the top pair stores the actual top value.

Therefore, returning the first field correctly implements top().

Minimum Operation

According to the invariant, the second field of the top pair contains the minimum of the complete current stack.

Therefore, returning the second field correctly implements getMin().

Because each operation performs only a fixed number of stack accesses, comparisons, and assignments, every operation runs in O(1) time.

Complexity Analysis

Let n be the maximum number of elements stored in the stack.

Time Complexity

Constructor

The constructor initializes an empty stack:

O(1)

push(val)

The method performs:

• One empty check
• At most one access to the current top
• One minimum comparison
• One stack insertion

Each operation takes constant time.

O(1)

pop()

Removing the top stack entry takes constant time:

O(1)

top()

Reading the first value from the top pair takes constant time:

O(1)

getMin()

Reading the second value from the top pair takes constant time:

O(1)

Therefore, every required operation satisfies the constant-time requirement.

Space Complexity

The stack stores one pair for every pushed element that has not been removed.

Each pair contains two integers:

(actual value, minimum for this state)

Although each pair uses constant space, the number of pairs grows with the number of elements in the stack.

In the worst case, the stack stores n pairs.

Therefore, the total auxiliary space complexity is:

O(n)

Storing two integers per element changes only the constant factor. It does not change the asymptotic complexity.

Corrected Solution: Store the Current Minimum with Each Value

Each stack entry stores a pair:

(actual value, minimum value at this stack state)

The first field contains the value pushed into the stack. The second field contains the minimum value among that entry and every entry below it.

#include <algorithm>
#include <stack>
#include <utility>

class MinStack {
private:
    std::stack<std::pair<int, int>> st;

public:
    MinStack() = default;

    void push(int val) {
        if (st.empty()) {
            st.push({val, val});
            return;
        }

        int currentMinimum = std::min(val, st.top().second);
        st.push({val, currentMinimum});
    }

    void pop() {
        st.pop();
    }

    int top() {
        return st.top().first;
    }

    int getMin() {
        return st.top().second;
    }
};

Walkthrough

Consider the following operations:

push(1)
push(2)
push(0)
getMin()
pop()
top()
getMin()

The stack stores pairs in the form:

(actual value, minimum at this state)

Initial State

Stack: empty

Operation 1: push(1)

The stack is empty, so 1 is both the actual value and the current minimum.

Top    (1, 1)

Operation 2: push(2)

The previous minimum is 1.

min(2, 1) = 1

The new pair is:

(2, 1)

The stack becomes:

Top    (2, 1)
Bottom (1, 1)

Operation 3: push(0)

The previous minimum is 1.

min(0, 1) = 0

The new pair is:

(0, 0)

The stack becomes:

Top    (0, 0)
       (2, 1)
Bottom (1, 1)

Operation 4: getMin()

The second field of the top pair is:

0

Therefore:

getMin() returns 0

Operation 5: pop()

The pair (0, 0) is removed.

The stack becomes:

Top    (2, 1)
Bottom (1, 1)

The previous minimum does not need to be recalculated. It was already stored in the pair (2, 1).

Operation 6: top()

The first field of the top pair is:

2

Therefore:

top() returns 2

Operation 7: getMin()

The second field of the top pair is:

1

Therefore:

getMin() returns 1

The complete output is:

[null, null, null, null, 0, null, 2, 1]

Common Mistakes

Scanning the Entire Stack in getMin()

Searching every element can find the correct minimum, but it requires:

O(n)

time.

The problem requires getMin() to run in:

O(1)

The minimum must therefore be maintained during push and restored during pop.

Tracking Only One Minimum Variable

A single variable remembers the current minimum but does not necessarily remember the previous minimum after that value is removed.

For example:

push(5)
push(2)
pop()

After removing 2, the minimum must return to 5.

Without additional state, determining that value would require scanning the stack.

Comparing the New Value with the Top Value

The new minimum must be calculated using the previous minimum:

std::min(val, st.top().second)

It must not be calculated using only the previous top value:

std::min(val, st.top().first)

The top value is not necessarily the minimum of the existing stack.

For example, the stack may contain:

1, 5

The top value is 5, but the minimum is 1.

Using Array Indexing on a Pair

This is invalid:

st.top()[0]
st.top()[1]

A std::pair uses named fields:

st.top().first
st.top().second

Forgetting the Empty-Stack Case in push

When the first value is pushed, no previous minimum exists.

The first pair must therefore be:

(val, val)

Attempting to access st.top() while the stack is empty would be invalid.

Reporting O(1) Space Complexity

Each individual pair uses constant space, but the stack may contain up to n pairs.

Therefore, the total auxiliary space complexity is:

O(n)

Constant space per element does not mean constant total space.

Key Takeaways

• A stack follows Last-In, First-Out order and naturally supports rollback-style operations.
• A normal stack already provides push, pop, and top in O(1) time.
• A single minimum variable cannot always restore the previous minimum after a pop.
• Storing (value, minimum at this state) creates a snapshot of the minimum at every stack position.
• Removing the top pair automatically restores the minimum stored in the previous state.
• Every required operation runs in O(1) time.
• The stack stores up to n pairs, so the total auxiliary space complexity is O(n).