In this blog post, we'll explore the design and implementation of a special kind of stack called a MinStack. The MinStack supports the usual stack operations such as push, pop, and top, but it also provides a method to retrieve the minimum element in constant time, O(1).

Understanding the Problem

Before diving into the implementation details, let's understand the problem statement.

We are required to implement the MinStack class with the following functionalities:

1. push(val): Adds the element val to the top of the stack.
2. pop(): Removes the element from the top of the stack.
3. top(): Returns the element present at the top of the stack without removing it.
4. getMin(): Returns the minimum element present in the stack.

The crucial requirement is that all these operations must have a time complexity of O(1).

Approach

To achieve O(1) time complexity for all operations, we need to maintain additional information alongside the main stack. Specifically, we'll maintain a separate stack to keep track of the minimum element at any given point in the main stack.

Let's walk through the implementation provided in the code snippet and understand each method:

class MinStack:

    def __init__(self):
        # Initialize the main stack and the auxiliary stack to track minimums.
        self.stack = []
        self.minStack = []

    def push(self, val: int) -> None:
        # Push the value onto the main stack.
        self.stack.append(val)
        
        # Update the minimum stack.
        if self.minStack:
            val = min(self.minStack[-1], val)
        self.minStack.append(val)

    def pop(self) -> None:
        # Remove the top element from both the main stack and the minimum stack.
        self.stack.pop()
        self.minStack.pop()

    def top(self) -> int:
        # Return the top element of the main stack.
        return self.stack[-1]

    def getMin(self) -> int:
        # Return the top element of the minimum stack, which represents the minimum element in the main stack.
        return self.minStack[-1]

Explanation

Initialization:

• We initialize two empty stacks: stack to hold the main elements and minStack to track the minimums.

Push Operation (push(val)):

• We add the given value val to the main stack.
• If the minStack is not empty, we compare the current value with the top element of minStack to determine the new minimum value.
• We then push this new minimum value onto the minStack.

Pop Operation (pop()):

• We simply pop the top element from both the main stack and the minStack.

Top Operation (top()):

• We return the top element of the main stack without removing it.

Get Minimum Operation (getMin()):

• We return the top element of the minStack, which represents the minimum element present in the main stack.

Conclusion

In conclusion, we have successfully designed and implemented a MinStack that supports all required operations in constant time complexity. By maintaining an additional stack to track the minimums, we've ensured efficient retrieval of the minimum element at any point. This solution is efficient and meets the requirements of the problem statement.