Problem Statement in English

Your task is to create a class called MinStack. It should support the following operations and perform them with the specified time complexities:

  • push within $O(1)$
  • pop within $O(1)$
  • top within $O(1)$
  • getMin within $O(1)$

Approach

All operations in the requirements are straightforward, except for getMin. Achieving this in $O(1)$ doesn’t appear to be so easy. How do know the minimum element in constant time when the stack is popped? Well, it’s not that bad.

Just push the current min along with every new value you push into the stack.

Maintain a min var in the MinStack class, and everytime you’re about to push a new element to the stack, first check if it’s lesser than the current min. If it is, then update the global min, and push the new min along with the value that was supposed to go into the stack.

We essentially store an extra piece of information along with every value that we push into the stack.

Solution in Python


from collections import deque

class MinStack:

    def __init__(self):
        self.min = None
        self.stack: deque[tuple[int,int]] = deque()

    def push(self, val: int) -> None:
        if self.min is None:
            self.min = val
        elif self.min > val:
            self.min = val
        self.stack.append((val, self.min))

    def pop(self) -> None:
        self.stack.pop()
        if len(self.stack) > 0:
            self.min = self.stack[-1][1]
        else:
            self.min = None

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

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

Complexity

  • Time: As specified by the question

  • Space: $O(n)$
    Since we store $n$ values at most.

And we are done.