Breaking Down the Stack Family: Valid Parentheses to LRU Cache

Second pattern in my interview grind: the stack family. What I like about this chain is that every problem answers a why — why a stack and not a counter, why indexes and not characters, why two structures and not one. If you can narrate those whys, the follow-ups stop being scary.

20. Valid Parentheses

An opening bracket waits until its closing bracket arrives. Last opened, first closed — that's LIFO, that's a stack.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        closeToOpen = {")": "(", "]": "[", "}": "{"}
 
        for ch in s:
            if ch in closeToOpen:
                if stack and stack[-1] == closeToOpen[ch]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(ch)
 
        return len(stack) == 0

Time: O(n) / Space: O(n)

Two traps: if stack and ... — without the empty check, ")(" crashes; and the final len(stack) == 0 — surviving the loop isn't enough, "(((" leaves unclosed openers behind.

Follow-up: One Bracket Type → a Counter Is Enough

If the string only has (), any open matches any close — you don't need to know which, only how many. A stack degrades into a counter:

def isValid(s):
    count = 0
    for ch in s:
        count += 1 if ch == '(' else -1
        if count < 0:          # a ')' arrived with nothing open
            return False
    return count == 0

Two rules: never go negative mid-scan (order violation, ")("), and end at zero (unclosed openers, "((("). The counter is literally "how many are still open" — the stack's height without the stack.

Count problems take a counter, order problems take a stack. The moment multiple types exist, "how many" isn't enough — you need "which was opened most recently," and that's exactly what a stack remembers. "([)]" passes every count check and is still invalid.

1249. Minimum Remove to Make Valid Parentheses

The real interview version of this chain — instead of judging the string, fix it. The insight: validity only needs matching, but deletion needs positions. So the stack stores indexes.

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        s = list(s)          # strings are immutable — work on a list
        stack = []           # indexes of unmatched '(' so far
 
        for i, ch in enumerate(s):
            if ch == '(':
                stack.append(i)
            elif ch == ')':
                if stack:
                    stack.pop()
                else:
                    s[i] = ''      # unmatched ')' — delete NOW
 
        for i in stack:            # unmatched '(' — known only at the end
            s[i] = ''
 
        return ''.join(s)

Time: O(n) / Space: O(n)

There's a nice asymmetry worth saying out loud: an unmatched ) is known invalid the moment it appears — delete it immediately. An unmatched ( is only known at the very end — that's exactly why its index waits on the stack. The s[i] = '' trick (empty strings vanish in join) is reusable in plenty of string problems.

Follow-up: Multiple Bracket Types

First, a clarifying question that completely changes the problem: "Is '([)]' invalid (proper nesting), or is each type validated independently?" If types are independent, per-type counters finish the job. For proper nesting, generalize the stack to (index, char) and check the top's type:

class Solution:
    def makeValid(self, s: str) -> str:
        s = list(s)
        stack = []
        close = {')': '(', ']': '[', '}': '{'}
 
        for i, ch in enumerate(s):
            if ch in '([{':
                stack.append((i, ch))
            elif ch in close:
                if stack and stack[-1][1] == close[ch]:
                    stack.pop()
                else:
                    s[i] = ''
 
        for i, _ in stack:
            s[i] = ''
 
        return ''.join(s)

Time: O(n) / Space: O(n)

And one caveat to volunteer before being asked: this greedy guarantees a valid result, but not the minimum removals. On "([)" it deletes all three characters, when deleting just [ gives "()" — one deletion. The problem is that "who's at fault — the closer, or the opener stuck in between?" depends on what comes later in the string. Greedy commits immediately and can't take it back.

Local decisions safe → greedy. Future-dependent decisions → DP. The true-minimum version is interval DP — dp[i][j] = min deletions for s[i..j], either delete s[i] or match it with every possible partner s[k] — which lands at O(n³). Knowing where the greedy's guarantee ends is the senior-level answer here.

155. Min Stack

Design a stack where push, pop, top, and getMin are all O(1). The instinct to fight: computing the min on demand is O(n). Don't compute — store.

Why not just one minValue variable? Because pop is an undo, and undo needs history. Push 3, push 1, pop — the variable says 1, but what was min before? Gone. So keep the whole history in a second stack:

class MinStack:
    def __init__(self):
        self.stack = []
        self.minStack = []
 
    def push(self, val: int) -> None:
        self.stack.append(val)
        if self.minStack:
            self.minStack.append(min(val, self.minStack[-1]))
        else:
            self.minStack.append(val)
 
    def pop(self) -> None:
        self.stack.pop()          # both stacks always move together
        self.minStack.pop()
 
    def top(self) -> int:
        return self.stack[-1]
 
    def getMin(self) -> int:
        return self.minStack[-1]

All operations O(1) / Space: O(n)

The invariant: minStack[i] = minimum of everything up to height i. Yes, that means duplicates pile up (push 1 then 5 → minStack is [1, 1]) — that's intentional. Each entry answers "what's the min at this height," and popping both together restores the previous answer automatically.

Space-optimized variant — push to minStack only on a new minimum:

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.minStack or val <= self.minStack[-1]:
            self.minStack.append(val)
 
    def pop(self) -> None:
        val = self.stack.pop()
        if val == self.minStack[-1]:
            self.minStack.pop()

The <= is the trap interviewers watch for. With <, a duplicate minimum gets recorded once — then one pop erases the record while the other duplicate is still in the stack.

O(1)-extra-space variant — store differences instead of values. val - min goes on the stack, min lives in one variable, and a negative stored value is a flag meaning "the min changed here":

class MinStack:
    def __init__(self):
        self.stack = []
        self.minVal = None
 
    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.minVal = val
        else:
            self.stack.append(val - self.minVal)
            self.minVal = min(self.minVal, val)
 
    def pop(self) -> None:
        d = self.stack.pop()
        if d < 0:                      # a min-setter is leaving
            self.minVal -= d           # restore: old = min - d
 
    def top(self) -> int:
        d = self.stack[-1]
        return self.minVal if d < 0 else self.minVal + d
 
    def getMin(self) -> int:
        return self.minVal

The subtle part: positive entries decode as min + d, because their reference min is still current. Negative entries are the min — their reference got overwritten the moment they pushed, so their d instead remembers how to restore the old one (old = min - d). One practical note: val - min can overflow fixed-width integers — fine in Python, needs long in Java or Kotlin.

146. LRU Cache

The boss of this chain, and a top-frequency interview problem. The design narration matters more than the code — this is roughly how I'd say it:

1. get/put must be O(1) → a hashmap comes to mind first.
2. But this problem has eviction — when full, remove the oldest item. A hashmap has no notion of order; finding the oldest means scanning, O(n).
3. The structure that keeps order with O(1) insert and remove is a doubly linked list. Doubly, because unlinking a middle node needs both neighbors — a singly linked list would spend O(n) finding the previous node.
4. But a list alone can't find a key's node without scanning — O(n) again.
5. So combine them: the hashmap's value points directly at the node. The map answers "where is this key," the list answers "who is oldest."

Left end = oldest, right end = newest, and two dummy nodes sit as fixed bookends so remove/insert never worry about empty-list edge cases — real nodes only ever live between them.

class Node:
    def __init__(self, key, val):
        self.key = key          # key too — eviction must delete from the map
        self.val = val
        self.prev = None
        self.next = None
 
 
class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}              # key -> Node
 
        self.left = Node(0, 0)       # dummy: oldest side
        self.right = Node(0, 0)      # dummy: newest side
        self.left.next = self.right
        self.right.prev = self.left
 
    def _remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next = nxt
        nxt.prev = prev
 
    def _insert(self, node):
        prev = self.right.prev
        prev.next = node
        node.prev = prev
        node.next = self.right
        self.right.prev = node       # ← the 4th pointer — don't forget it
 
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)           # using it = moving it to newest
        self._insert(node)
        return node.val
 
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
 
        node = Node(key, value)
        self.cache[key] = node       # register in BOTH structures
        self._insert(node)
 
        if len(self.cache) > self.cap:
            lru = self.left.next     # oldest sits next to the left dummy
            self._remove(lru)
            del self.cache[lru.key]  # lru's key — NOT the key just put

get/put O(1) / Space: O(capacity)

Every operation is a combination of two moves — unlink a node, insert at the newest spot — which is why the helpers exist. Worth announcing that upfront: the duplication is predictable from the design, so extracting helpers before coding reads as planning, not cleanup.

Every bug I hit wiring this was the same shape: the two structures falling out of sync. Forgot the fourth pointer in _insert (a doubly-linked insert rewires four pointers — count them). Inserted into the list but never registered in the map. Evicted with del self.cache[key] instead of lru.key — deleting the fresh entry while the evicted node haunts the map. That last one is the entire reason nodes store their key. My checklist now: four pointers? both structures? whose key?

Follow-ups that orbit this problem: "would you use OrderedDict in real code?" (yes — it's the same hashmap + linked list underneath, but interviewers want the internals shown once), "thread safety?" (a single mutex around get/put; Android's LruCache class ships synchronized), and "what about LFU?" (evict by frequency instead of recency — needs a frequency-bucket layer on top, LC 460, a genuinely harder problem).

Summary

The thread through all of it: every structure earns its place by answering a question the previous one couldn't. If you can tell that story out loud while coding, the follow-ups become the easy part.