Implementing a Min Stack in Python

Implementing a Min Stack in Python: From Basic to Optimized

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.

Let's explore a Python implementation of a MinStack, starting with a basic version and transitioning to a more optimized solution.

Understanding the Basic Implementation

Let's first look at a non-optimized implementation of MinStack:

class MinStack:

    def __init__(self):

        self._data = [] # Stores stack elements

        self._res = [] # Stores the minimum at each level


    def is_empty(self):

        return len(self._data) == 0


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

        self._data.append(val)

        min_val = min(val, self._res[-1] if self._res else val)

        self._res.append(min_val)


    def pop(self) -> None:

        self._data.pop()

        self._res.pop()


    def top(self) -> int:

        return self._data[-1]


    def getMin(self) -> int:

        return self._res[-1]

Explanation of the Basic Implementation

1. __init__: Initializes two stacks: _data for the actual elements and _res for tracking the minimum values.
2. push(val): Adds val to _data and updates _res with the minimum value so far.
3. pop(): Removes the top element from both _data and _res.
4. top(): Returns the last inserted element.
5. getMin(): Retrieves the minimum element in constant time.

While functional, this version has room for improvement, particularly regarding naming conventions and minor optimizations.

Optimized Implementation

Here's an optimized version with cleaner structure and improved readability:

class MinStack:

    def __init__(self):

        self.stack = [] # Main stack for storing elements

        self.min_stack = [] # Stack for tracking minimum values


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

        self.stack.append(val)

        min_val = min(val, self.min_stack[-1] if self.min_stack else val)

        self.min_stack.append(min_val)


    def pop(self) -> None:

        if self.stack:

            self.stack.pop()

            self.min_stack.pop()


    def top(self) -> int:

        return self.stack[-1] if self.stack else None


    def getMin(self) -> int:

        return self.min_stack[-1] if self.min_stack else None

Key Optimizations

1. Improved Naming: _data and _res are renamed to stack and min_stack for clarity.
2. Better Edge Case Handling:
   • Added checks in pop() to ensure elements exist before popping.
   • Used None return values in top() and getMin() when the stack is empty.
3. Efficiency Remains O(1): they have O(1) time complexity for push(), pop(), top(), and getMin().

Why this optimization?

The optimized version has various advantages that include:-

1) Improve code readability

2) Reduce potential errors.

3) It ensures stability when handling edge cases

This approach helps you efficiently manage minimum values when dealing with stacks without compromising performance.

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.