Implementing a Min Stack in Python

Implementing a Min Stack in Python: From Basic to Optimized

A Min-Stack is an advanced stack variant that allows us to retrieve the minimum element in constant time (O(1)), in addition to standard stack operations (push, pop, top). This structure is particularly valuable in problems requiring dynamic minimum tracking, such as sliding window algorithms and coding interviews (e.g., LeetCode 155).

Why a Min-Stack?

Traditional stacks do not provide a direct way to access the current minimum without scanning all elements (O(n)). A Min-Stack optimizes this by maintaining additional state so that getMin() is always available in O(1) time.

Efficiently tracking the minimum value in a stack is a common problem in data structures.

A naive approach would require scanning the stack every time the minimum value is needed, which is inefficient.

Approaches to Implementing a Min-Stack

Method 1: Auxiliary Stack

This method uses a second stack to track minimum values.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x: int):
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

• Time Complexity: O(1) for all operations.

• Space Complexity: O(n) extra for min_stack.

Method 2: Single Stack with Encoded Min

This method embeds previous minima within the main stack, using an auxiliary variable to keep track.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_val = None

    def push(self, x: int):
        if self.min_val is None or x <= self.min_val:
            self.stack.append(self.min_val)
            self.min_val = x
        self.stack.append(x)

    def pop(self):
        popped = self.stack.pop()
        if popped == self.min_val:
            self.min_val = self.stack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_val

• Time Complexity: O(1).

• Space Complexity: O(n), but avoids a full separate stack.

Method 3: Pair-Based Stack

Each element in the stack holds both the actual value and the current minimum.

class MinStack:
    def __init__(self):
        self.stack = []

    def push(self, x: int):
        curr_min = x if not self.stack else min(x, self.stack[-1][1])
        self.stack.append((x, curr_min))

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1][0]

    def getMin(self):
        return self.stack[-1][1]

• Time Complexity: O(1).

• Space Complexity: O(n).

Performance Analysis

All methods guarantee O(1) time complexity for push, pop, top, and getMin operations. Their main difference lies in space trade-offs and implementation complexity.

Example Workflow (Pair-Based)

1. Push(3) → Stack: [(3, 3)]

2. Push(2) → Stack: [(3, 3), (2, 2)]

3. Push(1) → Stack: [(3, 3), (2, 2), (1, 1)]

4. Pop() → Stack: [(3, 3), (2, 2)]

• After third push, getMin() returns 1.

• After pop, getMin() returns 2.

Use Cases

• Maintaining minimum values in sliding window problems.

• Interview coding challenges (e.g., LeetCode 155).

• Real-time systems requiring quick access to minima.

Conclusion

Implementing a Min-Stack enhances the power of traditional stacks by supporting real-time minimum tracking. Depending on your priorities (simplicity, space efficiency, or clarity), you can choose the method that best fits your needs

What's Next?

Understanding stack-based optimizations is essential for technical interviews and real-world applications.

To deepen your knowledge, you can explore stack problems like evaluating postfix expressions or implementing LRU caches.