Min Stack

The problem description can be found in LeetCode.

Approach

The idea here is to keep two stacks. One will be used to keep every value that goes into the push method. The second one will be used to keep only the minimum values instead.

Solution

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

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

    def pop(self) -> None:
        val = self.stack.pop()
        if self.getMin() == val:
            _ = self.min_stack.pop()

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

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

Complexity

For the single operation, we would have the following complexities:

• push:
  • Time: $O(1)$
  • Space: $O(1)$
• pop:
  • Time: $O(1)$
  • Space: $O(1)$
• top:
  • Time: $O(1)$
  • Space: $O(1)$
• getMin:
  • Time: $O(1)$
  • Space: $O(1)$