Problem statement

Brute force

We can use a Python list to act as a stack such that the push, pop, and top operations all require $O(1)$ time. The getMin operation can be implemented through a linear search, but this requires $O(n)$ time where $n$ is the length of the stack.

We can do better.

Optimized solution

To bring the time complexity of the getMin operation down to $O(1)$, we use two stacks: one stack to store the actual values and another stack to store the cumulative minimums of the first stack.

For example, consider the following input sequence of operations and the resulting output (if any) and the values contained in both stacks after the operation is completed:

  1. push(1): output: None, stack: [1], cum_min_stack: [1].
  2. push(2): output: None, stack: [1, 2], cum_min_stack: [1, 1].
  3. push(0): output: None, stack: [1, 2, 0], cum_min_stack: [1, 1, 0].
  4. push(1): output: None, stack: [1, 2, 0, 3], cum_min_stack: [1, 1, 0, 0].
  5. getMin(): output: 0, stack: [1, 2, 0, 3], cum_min_stack: [1, 1, 0, 0].
  6. pop(): output: None, stack: [1, 2, 0], cum_min_stack: [1, 1, 0].
  7. pop(): output: None, stack: [1, 2], cum_min_stack: [1, 1].
  8. top(): output: 2, stack: [1, 2], cum_min_stack: [1, 1].
  9. getMin(): output: 1, stack: [1, 2], cum_min_stack: [1, 1].

We see that stack contains the actual values while cum_min_stack[i] = min(stack[0:i]), and so we can obtain the minimum value in the stack as the top of the cum_min_stack.

Because getMin() would involve checking the top of cum_min_stack, it would involve only $O(1)$ time, as desired.

We implement the MinStack class in Python as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

    def push(self, val: int) -> None:
        self.stack.append(val)
        if len(self.cum_min_stack) == 0:
            self.cum_min_stack.append(val)
        else:
            self.cum_min_stack.append(min(val, self.cum_min_stack[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.cum_min_stack.pop()

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

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