Min Stack

01 · Question

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

02 · Analysis

Invariant: mins stores every new or tied minimum. Use <= on push so duplicate minima survive one pop. For example, push 2 twice and pop once: the minimum must still be 2. pop, top, and getMin require a nonempty stack. Push/pop are amortized O(1) with dynamic arrays; top/getMin are O(1). Space is O(n).

03 · Solution

Reference solution

1class MinStack:
2    def __init__(self):
3        self.stack = []
4        self.mins = []
5
6    def push(self, val: int) -> None:
7        self.stack.append(val)
8        if not self.mins or val <= self.mins[-1]:
9            self.mins.append(val)
10
11    def pop(self) -> None:
12        val = self.stack.pop()
13        if val == self.mins[-1]:
14            self.mins.pop()
15
16    def top(self) -> int:
17        return self.stack[-1]
18
19    def getMin(self) -> int:
20        return self.mins[-1]

Longest Balanced Subsequence

Evaluate Reverse Polish Notation