Day two: the stack family — Valid Parentheses and its follow-up chain, Min Stack a few different ways, and LRU Cache. Less about solving, more about why each data structure earns its place.
- Count problems take a counter, order problems take a stack — with one bracket type any open matches any close, but once there are multiple types you need to know which one opened most recently, and that's exactly what a stack remembers
- Min Remove to Make Valid stores indexes on the stack instead of characters, because validity only needs matching but deletion needs positions
- An unmatched closing bracket is invalid the moment it shows up, so delete it right away — an unmatched opening bracket is only known at the very end, which is why its index waits on the stack until then
- The greedy version of Min Remove guarantees a valid result, not the minimum number of removals — when a decision depends on what comes later in the string, that's DP territory, not greedy
- Min Stack needs a second stack, not just one min variable — popping is an undo, and undoing needs history, not just the current value
- The O(1)-space version of Min Stack stores the difference between each value and the min instead of the value itself — a negative difference is a flag that the min changed at that point
- LRU Cache is two structures covering each other's blind spot: a hashmap for O(1) lookup, and a doubly linked list to track which item is oldest, since a hashmap alone has no sense of order
- Every bug I hit wiring the LRU cache was the same shape — the linked list and the hashmap fell out of sync because I updated one and forgot the other