PatternsPractice and reference
Look-alike problems
The fastest way to misuse a pattern is to forget the condition that made it work. Use these pairs as deliberate comparisons. Before you study the second solution, explain which assumption changed.
| First problem or condition | What changes | What to rethink |
|---|---|---|
| Shortest window with positive numbers, LC 209 | Negative numbers allowed, LC 862 | A bigger window no longer means a bigger sum; use prefix sums with a monotonic deque |
| Range sums on a fixed list, LC 303 | Values change, LC 307 | Prefix sums computed once versus a structure you can update |
| Any matching pair, LC 1 | Unique triples, LC 15 | Trying values, handling duplicates, and two pointers on a sorted list |
| Shortest path, every edge the same cost | Different costs, none negative, LC 743 | BFS order versus Dijkstra's closest-first order |
| Cheapest route with no limits | Limited stops, LC 787 | The node alone versus the node plus the stops left |
| Most intervals, LC 435 | Intervals have rewards, LC 1235 | "Earliest end first" no longer protects the total reward |
| Each item at most once, LC 416 | Coins can be reused, LC 518 | What the state means, and which direction to update |
| Coin combinations, LC 518 | Ordered sums, LC 377 | Whether different orders count as different answers |
| Subsequence, LC 1143 | Contiguous substring, LC 718 | Skipping is allowed in one recurrence and not the other |
| Reachability in a grid, LC 200 | Keys change your moves, LC 864 | Position alone no longer captures the state |
| Kth largest, values only added, LC 703 | Values can be deleted | A dropped value may matter again |
| Two strings that look equal | Their hashes match | Equal hashes need a plan for collisions |
These pairs are for comparing ideas. They don't all differ in only one detail, so read both problems in full, including the output format and limits.
What you claim stays true must be specific enough to prove the result. "The stack is sorted" doesn't explain why popped items aren't needed. "The DP stores the best answer" doesn't say what the subproblem is. "Every settled distance is the shortest" needs the graph's assumptions and a rule for when to settle.
Test each technique you learn in three ways: change what the input can contain, change what you're asked for, and change which operations are allowed. Positive to negative, "does one exist" to "how many", and adding to deleting each expose a different hidden assumption.