Problem overview
A stack gives values back in reverse order: the last value pushed is the first one popped. The class MinStack must behave like a stack and also answer getMin(), the smallest value it holds right now, without removing anything. Every operation (push, pop, top, getMin) has to take constant time, and the constraints allow up to 200,000 calls, so a scan over the whole stack in getMin is too slow.
Take the first example: push -2, 0 and -3. The stack holds [-2, 0, -3], with -3 on top, so getMin() is -3. After pop() removes -3, the top is 0 and the smallest value is -2 again. The minimum that left took its place with it, and the old one came back.
Approach: remember the minimum at every depth
The obvious shortcut is one extra variable holding the smallest value seen. It fails on the first example. After pop() removes -3, the variable would still say -3, and nothing tells the class what the minimum was before -3 arrived. Searching the stack for the new minimum would bring back the O(n) cost.
The way out is a fact about stacks: a value leaves only after every value above it has left. While a value sits in the stack, the values below it cannot change. So the smallest value from the bottom up to that position can be computed once, when the value is pushed, and written down next to it. The class keeps two lists of the same length:
stackholds the values themselves, with the top at the end of the list.minStackholds, at each depth, the smallest of the value at that depth and everything below it.
The last entry of minStack therefore describes the whole stack as it is now, and popping removes it together with its value, which uncovers the previous minimum. For the pushes -2, 0, -3 the two lists are [-2, 0, -3] and [-2, -2, -3]. After the pop they are [-2, 0] and [-2, -2], and the minimum is -2.
Step by step
- Create
self.stackin__init__. An empty list is enough. A list'sappendandpopboth work at its end, so the end of the list is the top of the stack. - Create
self.minStack. Another empty list, always the same length as the first one. - In
push, append the value toself.stack. The value goes on the ordinary stack, as on any stack. - Start
currentMinatval. If the stack was empty,valis its only value, so it is also the smallest. - If
self.minStackhas entries, take the smaller ofcurrentMinandself.minStack[-1]. That last entry is already the smallest of everything underval, so one comparison withminsettles it. An empty list counts as false, soif self.minStack:runs only when there is something below. - Append
currentMintoself.minStack. Both lists now have the same length. A value equal to the current minimum is recorded too, so a minimum pushed twice is remembered twice. - In
pop, pop from both lists. They must stay the same size. Removing the last entry ofminStackuncovers the minimum the stack had before that value arrived. - In
top, returnself.stack[-1]. Index -1 is the last element of a list, and reading it removes nothing. - In
getMin, returnself.minStack[-1]. The answer was prepared when the value was pushed.
The solution in Python
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val: int) -> None:
self.stack.append(val)
currentMin = val
if self.minStack:
currentMin = min(currentMin, self.minStack[-1])
self.minStack.append(currentMin)
def pop(self) -> None:
self.stack.pop()
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]
A few Python details are worth knowing:
- A list is a stack.
appendandpop()without an argument both work at the end of the list and take constant time on average. Popping from the front withpop(0)would shift every other element, so it is not used here. - Negative indexes.
self.stack[-1]reads the last element without needing the length. On an empty list it raisesIndexError, which is acceptable here becausepop,topandgetMinare only called on a non-empty stack. - Methods return nothing.
popin this class removes the top value and returnsNone. The list's ownpop()returns the removed value, but the class's method does not pass it on. - Integers have no overflow. Python integers grow as needed, so values at the edges of the 32-bit range need no special care.
Complexity
Every method does a fixed number of list operations at the end of a list, so each call takes O(1) time, matching the requirement. The two lists each hold one entry per value, so the extra space is O(n) for n values in the stack. The second list is the price for constant-time minimums: it doubles the memory but keeps getMin from ever looking through the stack.
Edge cases and common mistakes
- Keeping one minimum variable. It breaks as soon as the minimum is popped. On the pushes -2, 0, -3 followed by a pop, a single variable still reports -3 where the answer is -2.
- Duplicates of the minimum. Pushing 5, 5, 7 and then popping twice leaves one 5 in the stack, so
getMin()must still return 5. BecauseminStackgets an entry for every push, including a value that only equals the current minimum, the second 5 is remembered. A version that skips equal values loses it. - Letting the two lists drift apart. Pop from both lists every time and push to both every time. If the lengths differ, the entry at the top of
minStackno longer belongs to the value at the top ofstack. - Top is not the minimum. With the pushes 3, 1, 2,
top()returns 2 andgetMin()returns 1. After two pops, only 3 is left and it is the minimum again. - The first push.
self.minStack[-1]on an empty list would fail, which is why theif self.minStack:check comes first.
Testing
Try these in a file of your own, after the class definition:
s = MinStack()
for v in (-2, 0, -3):
s.push(v)
print(s.stack, s.minStack)
print(s.getMin())
s.pop()
print(s.top(), s.getMin())
Expected output:
[-2, 0, -3] [-2, -2, -3]
-3
0 -2
A second check with duplicates:
t = MinStack()
for v in (5, 5, 7):
t.push(v)
t.pop()
t.pop()
print(t.getMin(), t.top(), t.stack, t.minStack)
5 5 [5] [5]
