algoadvance

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

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Clarifying Questions

1. Are there any constraints on the values that can be pushed onto the stack?
   • No, the problem does not specify any constraints on the values.
2. Is there any limit to the size of the stack?
   • No, the problem does not specify any size limits for the stack.
3. What should be the behavior if pop or top is called on an empty stack?
   • Since this is a typical interview question, we can assume the stack is not empty when pop or top is called. Otherwise, we may need to handle exceptions or errors appropriately.

Strategy

To keep track of the minimum element in constant time, we can use an auxiliary stack that maintains the current minimum elements. Here’s how we can design the MinStack:

• Use two stacks:
  • main_stack to store the actual values.
  • min_stack to store the minimum values at each level.
• When a new value is pushed onto the main_stack:
  • Also push it onto the min_stack if it is smaller than or equal to the current minimum element, or if the min_stack is empty.
• When a value is popped from main_stack:
  • Also pop from the min_stack if the popped value is the same as the current minimum.

• The top operation returns the top of the main_stack.

• The getMin operation returns the top of the min_stack.

By doing this, we ensure that all operations run in constant time, O(1).

Code

class MinStack:
    def __init__(self):
        self.main_stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.main_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.main_stack:
            top_value = self.main_stack.pop()
            if top_value == self.min_stack[-1]:
                self.min_stack.pop()

    def top(self) -> int:
        if self.main_stack:
            return self.main_stack[-1]
        return None # Should not happen, as per our assumptions.

    def getMin(self) -> int:
        if self.min_stack:
            return self.min_stack[-1]
        return None # Should not happen, as per our assumptions.

Time Complexity

• push(val): O(1) because appending to both stacks is a constant-time operation.
• pop(): O(1) because popping from both stacks is a constant-time operation.
• top(): O(1) because accessing the last element is a constant-time operation.
• getMin(): O(1) because accessing the last element in the min_stack is a constant-time operation.

This design ensures that all required operations are performed in constant time, meeting the problem’s requirements.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?