L4. Implement Min Stack | Stack and Queue Playlist

Designing a Min Stack requires building a standard stack data structure that supports typical operations (push, pop, top, and size) alongside an efficient getMin() operation in constant time $O(1)$. While standard built-in stacks do not provide a getMin() method out-of-the-box, this comprehensive guide explores both the standard pair-based approach and the space-optimized mathematical encoding approach.

1. Problem Statement & Requirements

A standard stack allows engineers to push elements, pop elements, inspect the top element, and check its size. However, finding the minimum element across standard stack implementations typically requires scanning all elements linearly, resulting in an unacceptable $O(N)$ time complexity.

The goal is to design a MinStack class supporting the following interface in $O(1)$ time complexity:

• push(val): Pushes element val onto the stack.
• pop(): Removes the element on top of the stack.
• top(): Gets the top element of the stack without removing it.
• getMin(): Retrieves the minimum element currently present in the stack in $O(1)$ time.

2. Approach 1: The Pair-Based Intuitive Approach ($O(2N)$ Space)

Core Mental Model

Instead of storing a single integer in our stack nodes, what if we modify the stack to store a pair of integers (value, minimum_so_far)?

• The first element of the pair represents the actual value pushed.
• The second element tracks the minimum value encountered in the stack from the bottom up to that specific point.

Step-by-Step Flow Walkthrough

1. Push 12: Stack is empty. No previous minimum exists. We push (12, 12).
2. Push 15: Current minimum of the stack top is 12. Comparing 15 with 12, the minimum remains 12. We push (15, 12).
3. Push 10: Current minimum of the stack top is 12. Comparing 10 with 12, the minimum changes to 10. We push (10, 10).
4. getMin(): Inspect the top pair's second element directly: 10.
5. pop(): Removes (10, 10) from the stack.
6. top(): Inspect the new top pair's first element: 15.
7. getMin(): Inspect the new top pair's second element directly: 12.

Code Implementation (Pseudo-code)

class MinStackPair {
    stack<pair<int, int>> st;

public:
    void push(int val) {
        if (st.empty()) {
            st.push({val, val});
        } else {
            int currentMin = min(val, st.top().second);
            st.push({val, currentMin});
        }
    }

    void pop() {
        if (!st.empty()) st.pop();
    }

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

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

Complexity Analysis

• Time Complexity: $O(1)$ for push, pop, top, and getMin().
• Space Complexity: $O(2N)$ because every stack node stores two integers (the value and the minimum tracker).

3. Approach 2: The Space-Optimized Mathematical Encoding ($O(N)$ Space)

To optimize space down to a single integer per node ($O(N)$), we must avoid storing redundant minimum values. The key insight is: Can we mathematically encode past minimum history when a new minimum is introduced, and decode it during a pop operation?

The Mathematical Encoding Strategy

When a new value is smaller than our current minimum, it updates the minimum. Instead of pushing the raw value directly, we store a modified encoded value calculated as:

And we update our tracker variable minimum = val.

Why This Works (Mathematical Proof)

1. Since the new value val is strictly less than the previous_min, we know that:

2. Adding val to both sides:

3. This guarantees that the encoded value stored in the stack will always be strictly less than the current minimum (val).
4. During a pop() operation, if the popped element is less than the current minimum, we recognize it as an encoded flag and restore the previous_min using the inverse formula:

4. Complete Walkthrough of Space-Optimized Min Stack

Let's trace operations with initial minimum = INT_MAX:

5. Complete Optimized Code Implementation

Here is the fully functional, production-grade C++ implementation of the optimized Min Stack:

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

class MinStack {
    stack<long long> st;
    long long mini;

public:
    MinStack() {
        mini = __LONG_LONG_MAX__;
    }
    
    void push(long long val) {
        if (st.empty()) {
            mini = val;
            st.push(val);
        } else {
            if (val >= mini) {
                st.push(val);
            } else {
                // Mathematical encoding for new minimum
                st.push(2 * val - mini);
                mini = val;
            }
        }
    }
    
    void pop() {
        if (st.empty()) return;
        
        long long poppedVal = st.top();
        st.pop();
        
        // If popped value is less than current minimum, decode previous minimum
        if (poppedVal < mini) {
            mini = 2 * mini - poppedVal;
        }
    }
    
    int top() {
        if (st.empty()) return -1;
        
        long long topVal = st.top();
        // If topVal is less than mini, mini actually holds the real top value
        if (topVal < mini) {
            return mini;
        }
        return topVal;
    }
    
    int getMin() {
        if (st.empty()) return -1;
        return mini;
    }
};

6. Comparison of Approaches

7. Summary and Key Takeaways

• The Core Problem: Standard stacks lack an $O(1)$ getMin() operation because elements change order dynamically during pops.
• Naïve Solution Flaw: Scanning the stack linearly on every getMin() call takes $O(N)$ time, which is suboptimal.
• Pair Strategy: Storing pairs of (value, minimum_so_far) solves it in $O(1)$ time but doubles space complexity to $O(2N)$.
• Mathematical Optimization: By encoding new minimums using the formula $2 \times \text{val} - \text{previous\_min}$, we compress space down to single integers ($O(N)$ space).
• Flag Identification: Encoded values are always strictly smaller than the current minimum, acting as internal flags during pop() and top() resolutions.
• Overflow Prevention: Using long long integers in C++ prevents integer overflow issues when performing multiplication operations ($2 \times \text{val}$) near max integer limits.