Min Stack | Leetcode 155 | Optimal Solution in Python

If you want to master stack-related challenges and ace your coding interviews, understanding how to implement a Min Stack is crucial. This classic problem not only tests your ability to design efficient data structures but also sharpens your skills in managing auxiliary information within a stack to optimize queries.

Here’s the [Problem Link] to begin with.

In this comprehensive guide, we’ll look at the problem statement, walk through a carefully explained solution, and break down the time and space complexities, all presented with clarity to help beginners and experts alike.

Problem Statement

Design a stack that supports four operations, each in constant time (O(1)):

• push(val): Pushes the integer val onto the stack.
• pop(): Removes the element on the top of the stack.
• top(): Retrieves the top element of the stack without removing it.
• getMin(): Retrieves the minimum element in the entire stack at any point.

Your stack must efficiently keep track of the minimum element without the need to scan through the entire stack every time you call getMin().

Why Is This Challenging?

A usual stack supports push, pop, and top in constant time. But tracking the minimum element needs extra thought. The naive approach is this:

• On each getMin(), scan through the entire stack to find the minimum element, which costs O(n) time.
• This is inefficient and not acceptable for time-critical use cases or interview-level coding problems.

Our goal is to maintain all operations in O(1) time, including getMin(), which requires a specialized design.

Intuition and Approach: Storing Current Minimums Alongside Each Element

The key insight is to store, alongside every pushed element, the minimum element in the stack up to that point. This way, every element on the stack knows what the current minimum is when it was pushed.

How does this work?

1. When the stack is empty and we push the first element, the minimum is the element itself, so we store (value, value).
2. When pushing a new element, compare it to the minimum stored with the stack’s top element.
3. The new minimum is the smaller of:
   • The new element’s value
   • The current minimum
4. Push the pair (new value, new minimum) onto the stack.

Thus:

• getMin() simply returns the minimum stored with the top element.
• top() returns the value part of the top element.
• pop() removes the top element (and, implicitly, the minimum stored with it).

This design ensures constant-time retrieval of the minimum, with no extra traversal.

Detailed Code Implementation

class MinStack:
    def __init__(self):
        # Stack holds pairs: [element_value, current_min]
        self.stack = []

    def push(self, val: int) -> None:
        if len(self.stack) == 0:
            # If stack empty, min is val itself
            self.stack.append([val, val])
        else:
            # Current minimum is top element's min value
            current_min = self.stack[-1][1]
            # New minimum is smaller of val and current min
            new_min = min(current_min, val)
            self.stack.append([val, new_min])

    def pop(self) -> None:
        if self.stack:
            self.stack.pop()

    def top(self) -> int:
        if not self.stack:
            return None  # Or raise exception as per requirement
        # Return the value part of the top element
        return self.stack[-1][0]

    def getMin(self) -> int:
        if not self.stack:
            return None  # Or raise exception as per requirement
        # Return the min part of the top element
        return self.stack[-1][1]

Explanation of Each Operation

• push(val)
  Adds an element paired with the minimum value so far. It compares the value to the current minimum and decides which minimum to record for this level.
• pop()
  Removes the topmost pair. Both the value and the minimum associated with that state get removed, revealing the previous minimum beneath.
• top()
  Returns the latest pushed value without removing it.
• getMin()
  Returns the minimum element among all values currently in the stack instantly, thanks to the stored min information.

Example Breakdown

Consider a sequence of operations:

minStack = MinStack()
minStack.push(3)
minStack.push(5)
minStack.push(2)
minStack.push(1)
minStack.push(4)

Stack content (value, min):

• [ (3,3) ]
• [ (3,3), (5,3) ]
• [ (3,3), (5,3), (2,2) ]
• [ (3,3), (5,3), (2,2), (1,1) ]
• [ (3,3), (5,3), (2,2), (1,1), (4,1) ]

1. getMin() → returns 1 (top element min)
2. pop() → removes (4,1)
3. getMin() → still 1 (from (1,1))
4. pop() → removes (1,1)
5. getMin() → 2 (from (2,2))
6. top() → 2 (value of the top)

This shows how the stored minimum changes dynamically with push and pop.

Time and Space Complexity Analysis

This makes the stack scalable and performant even for large data sets or time-sensitive applications.

Real-World Applications

• Tracking minimum in dynamic datasets: Useful in algorithms that need quick min queries during data processing.
• Undo operations: Where you want to quickly recall states with min/max information.
• Financial or gaming apps: Where real-time minimums or maximums influence plays or strategy.

Conclusion

The Min Stack problem perfectly demonstrates how to augment a common data structure with auxiliary information to achieve efficient queries. By storing the current minimum with each pushed element, all operations, including minimum retrieval, remain constant-time. This technique is both elegant and practical for interview success and real-world system design.

For practice, try similar stack problems like Max Stack, or variations with constant-time median retrieval to deepen your understanding.