Min Stack - Leetcode Solution

Problem Statement:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) - Push element x onto stack.
• pop() - Removes the element on top of the stack.
• top() - Get the top element.
• getMin() - Retrieve the minimum element in the stack.

Approach:

The key to solving this problem is to maintain a separate stack which only stores the minimum elements. The minimum element stack keeps track of the minimum element at any given point of time.

Algorithm:

We can implement the Min Stack using two stacks - a main stack and a minimum stack.

• When an element is pushed onto the main stack, it is also compared to the element at the top of the minimum stack. If the minimum stack is empty or the element is smaller than or equal to the top of the minimum stack, the element is pushed onto the minimum stack.

• When an element is popped from the main stack, it is also compared to the element at the top of the minimum stack. If the element is equal to the top of the minimum stack, that element is popped from the minimum stack as well.

• To retrieve the minimum element in the stack, simply return the top element of the minimum stack.

• To retrieve the top element of the stack, simply return the top element of the main stack.

Let's look at the implementation in Python:

class MinStack:

def __init__(self):
    """
    initialize your data structure here.
    """
    self.stack = []
    self.min_stack = []

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

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

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

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

Time Complexity:

• The time complexity of push, pop, top, and getMin is O(1).

Space Complexity:

• The space complexity of Min Stack is O(n), where n is the total number of elements in the stack.

Conclusion:

In this article, we learned how to implement the Min Stack problem using two stacks. We also discussed the algorithm and the corresponding Python implementation.

1