Implementing a Min Stack

The Challenge: Constant-Time Minimum

A standard stack, whether implemented with an array or a linked list, naturally supports push, pop, and top (or peek) in $O(1)$ time. However, finding the minimum element is not a standard feature. A naive approach would be to iterate through all the elements in the stack whenever getMin is called. While simple, this would be an $O(n)$ operation, failing our primary constraint.

The challenge lies in storing extra information as we modify the stack, so that the current minimum is always immediately available.

The following video from NeetCode introduces the problem and explains why the naive approach falls short.

Approach 1: The Two-Stack Solution

The most common and intuitive solution involves using a second, auxiliary stack. Let's call our primary stack stack and our auxiliary stack min_stack.

The core idea is this: for every element in the main stack, the min_stack will store the minimum value found in the main stack up to that point.

Here's how the operations work:

• push(val):

  1. Push val onto the stack.
  2. Check the top of the min_stack. The new minimum is the smaller of val and the current minimum (which is at min_stack.top()). Push this new minimum onto the min_stack.
  3. If min_stack is empty, the new minimum is simply val.

• pop():

  1. Pop the element from the stack.
  2. Simultaneously, pop the corresponding minimum from the min_stack. This keeps the two stacks synchronized.

• top():

  1. Return the top element of the stack.

• getMin():

  1. Return the top element of the min_stack. Since this stack always holds the current minimum at its top, this is an $O(1)$ operation.

The image below illustrates the state of the stack and the current minimum after a sequence of push and pop operations, which is exactly what our min_stack would track at its top.

The NeetCode video you started provides an excellent visual walkthrough of this two-stack logic.

To reinforce this, the article from NeetCode.io provides a concise summary and a very clean Python implementation.

Here is a Python implementation of the MinStack class using this two-stack approach:

class MinStack:
    def __init__(self):



        # The main stack to store the actual elements
        self.stack = []



        # The auxiliary stack to store the minimum at each level
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)



        # Determine the new minimum and push it to the min_stack
        new_min = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(new_min)

    def pop(self) -> None:



        # Pop from both stacks to keep them in sync
        if self.stack:
            self.stack.pop()
            self.min_stack.pop()

    def top(self) -> int:
        if self.stack:
            return self.stack[-1]
        return None # Or raise an exception

    def getMin(self) -> int:
        if self.min_stack:
            return self.min_stack[-1]
        return None # Or raise an exception

This solution is elegant, easy to understand, and meets all the requirements. It has an $O(1)$ time complexity for all operations and an $O(n)$ space complexity due to the auxiliary stack. In most interview scenarios, this is the expected and perfectly acceptable solution.

Alternative Approaches and Trade-offs

For a deeper understanding and to prepare for follow-up questions, it's useful to know about other ways to solve this problem.

Approach 2: A Single Stack of Pairs

Instead of two separate stacks, you can use a single stack where each entry is a pair (or tuple): (value, current_minimum).

• When you push(val), you would append the pair (val, min(val, current_min_at_top)) to the stack.
• getMin() would then just return the second item from the pair at the top of the stack.

This approach is conceptually very similar to the two-stack method and has the same time and space complexity. The choice between them is often a matter of coding style. The article from GeeksforGeeks discusses this approach.

Approach 3: The O(1) Space Optimization (Advanced)

A clever, though more complex, solution exists that uses only one stack and a single variable to track the minimum, thus achieving $O(1)$ auxiliary space. This method involves encoding information into the values being pushed onto the stack.

• When pushing a new value x that is less than the current minimum minEle, instead of pushing x, you push a "fake" value (e.g., 2*x - minEle) and then update minEle = x.
• When popping, if the value you pop is less than minEle, you know it's a "fake" value, which signals that the minimum is about to change. You can then use the same formula to decode the previous minimum.

While this approach is a fascinating algorithmic puzzle, its complexity and potential for issues like integer overflow (as noted in the NeetCode.io article) make it less practical for a typical interview unless you are specifically asked to optimize for space. It's good to be aware that it exists as a testament to creative problem-solving.

Both the GeeksforGeeks and NeetCode.io articles provide excellent explanations of this advanced trick.

Conclusion

In this lesson, you have learned how to tackle a classic data structure design problem. The Min Stack is a perfect example of how interview questions test not just your knowledge of a data structure, but your ability to adapt it to meet new requirements efficiently.

Key Takeaways:

• A Min Stack must support push, pop, top, and getMin all in $O(1)$ time.
• A naive $O(n)$ iteration for getMin is too slow.
• The most common and effective solution uses an auxiliary stack to track the running minimum at every step, achieving $O(1)$ time for all operations at the cost of $O(n)$ extra space.
• Alternative designs exist, such as using a stack of (value, min) pairs or a complex $O(1)$ space solution, each with its own trade-offs. For interviews, clarity and correctness are often valued over the most complex optimization.

This lesson concludes our module on linear data structures. You've covered linked lists, stacks, and queues, along with advanced patterns like fast/slow pointers, monotonic stacks, and now custom designs like the Min Stack.

In our next module, we will shift gears to Searching and Sorting Algorithms. These are foundational algorithmic primitives that are not only essential on their own but also serve as building blocks for solving a vast range of more complex problems. We will start by implementing and analyzing the classic Merge Sort algorithm.