Day 15 · ~25 minutes · stack matching · Python
Tonight's problems are Valid Parentheses and Min Stack. Interviewers like them because they test one small question: when the newest thing must be resolved first, can you keep exactly that newest thing ready?
A stack remembers the most recent unresolved opener — exactly what bracket nesting needs; a shadow stack of running minima makes getMin O(1).
A stack is last-in, first-out: the last item pushed is the first item popped. In Python, a list already works as a stack with append and pop (Python docs: using lists as stacks).
The problem: a string has only brackets, and every closer must match the correct opener in the correct nesting order. A brute force approach is to repeatedly delete adjacent matched pairs: (), [], and {}. That can work, but it is O(n²): each cleanup pass scans the string again, and deeply nested input may need many passes.
The better question is sharper: when you see a closer, what opener is it trying to close? It must be the most recent unresolved opener. That is exactly the top of a stack.
The closer does not search the whole string; it checks the newest unresolved opener at the stack top.
def is_valid(s):
need = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch not in need:
stack.append(ch) # unresolved opener
elif not stack or stack.pop() != need[ch]:
return False # no opener, or wrong one
return not stack # nothing left unresolved
Notice the shape: push openers, pop only when a closer proves the top opener is the right one. If anything closes out of order, the invariant breaks immediately.
Min Stack: build a stack that supports push, pop, top, and getMin. Before opening the reveal, predict why one variable called min_value is not enough after pops.
A single variable forgets the previous minimum when the current minimum is popped. So every push also records the minimum at that exact depth.
The minimum stack changes in lockstep with the value stack, so getMin is just a peek at the top.
class MinStack:
def __init__(self):
self.vals, self.mins = [], []
def push(self, x):
self.vals.append(x)
best = x if not self.mins else min(x, self.mins[-1])
self.mins.append(best) # min as of this depth
def pop(self):
self.mins.pop()
return self.vals.pop()
def top(self):
return self.vals[-1]
def getMin(self):
return self.mins[-1]
The shadow stack moves in lockstep with the real stack. Pop a value, and you also pop the minimum that belonged to that depth.
| Problem | Approach | Time | Space |
|---|---|---|---|
| Valid Parentheses | Repeated pair removal | O(n²) | O(n) |
| Valid Parentheses | Stack matching | O(n) | O(n) |
| Min Stack | Scan for minimum | O(n) getMin | O(n) |
| Min Stack | Shadow minima | O(1) operations | O(n) |
1. Which action closes the newest unresolved opener?
2. Spot the bug in this closer branch:
elif stack[-1] == need[ch]:
stack.pop()
else:
return Falsestack[-1] crashes because there is no opener to inspect. Check not stack first.3. What should the shadow min stack store?
getMin can read the top of the shadow stack in O(1).4. Which problem uses opener matching directly?
Solve these on LeetCode, in order, logging each in your Notion tracker with the cycle — predict → attempt → compare → encode:
For the encode step, write the invariant at the top of this page in your own words. That line is what revision days will test.
Watch NeetCode — Valid Parentheses after your attempt, as the compare step. Listen for the moment he decides a closer must match the stack top.
Stuck or curious? Ask your teacher (the agent) — that's what it's for.