Min Stack LeetCode Solution to Problem 155 [Python]

An efficient Min Stack LeetCode problem solution in Python to problem #155, plus similar interview questions to it.

This problem involves designing a stack class that supports four operations: push, pop, top, and retrieving the minimum element in constant time.

We must implement these operations with O(1) time complexity.

Let’s break it down step by step.

Problem Overview

The problem requires designing a stack class that can perform the following operations:

1. push(val): Add an element val to the stack.
2. pop(): Remove the top element from the stack.
3. top(): Get the top element from the stack.
4. getMin(): Retrieve the minimum element from the stack.

The challenge here is to achieve a constant (O(1)) time complexity for each of these operations.

Efficient Min Stack LeetCode Solution

To solve this problem efficiently, we will use two stacks: one to store the elements (stack) and another to store the minimum values (minStack).

When we push an element onto the stack, we will also push the current minimum value onto the minStack.

This way, we can always access the minimum value in O(1) time.

Let’s see the Python code for the efficient solution:

class MinStack:
    def __init__(self):
        self.stack = []   # Stack to store elements
        self.minStack = []  # Stack to store minimum values

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.minStack or val <= self.minStack[-1]:
            self.minStack.append(val)

    def pop(self) -> None:
        if self.stack:
            if self.stack[-1] == self.minStack[-1]:
                self.minStack.pop()
            self.stack.pop()

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

    def getMin(self) -> int:
        if self.minStack:
            return self.minStack[-1]

This code efficiently maintains the minimum value in the minStack by comparing the current value with the top of the minStack when pushing. It also takes care of popping from both stacks.

Time and Space Complexity

The time complexity of our solution is O(1) for all four operations (push, pop, top, getMin) because we are using two separate stacks to maintain the minimum value.

The space complexity is O(n), where n is the number of elements pushed onto the stack.

Constraints

The problem constraints are as follows:

• Values (val) can range from -231 to 231 – 1.
• The pop, top, and getMin operations will always be called on non-empty stacks.
• There will be at most 30,000 calls to push, pop, top, and getMin.

Edge Cases a Valid Solution Must Consider

1. Pushing elements onto the stack.
2. Popping elements from the stack.
3. Getting the top element.
4. Retrieving the minimum element.

Related LeetCode Interview Questions

• Evaluate Reverse Polish Notation LeetCode
• Two Sum II LeetCode Problem
• Top K Frequent Elements LeetCode Problem
• Valid Parentheses LeetCode Problem
• Two Sum LeetCode Problem

Conclusion

In this blog post, we tackled the “Min Stack” LeetCode problem, which required designing a stack class that supports various operations with constant time complexity.

We provided an efficient Python solution using two stacks, one to store elements and the other to maintain the minimum values.

This solution meets the constraints and passes all edge cases, ensuring that all operations run in O(1) time.

If you have any questions, suggestions, or comments, feel free to ask in the comments section. You can find the original problem on LeetCode here. Happy coding!