Card 07/ 07
Recap: Choosing a Pattern
Structure first, then the question's shape, then what the values allow: each pattern is chosen by a property, never by a word.
A pattern is chosen by testing the problem for properties in a fixed order: the structure of the input, then the shape of the question, then what the values allow. A word in the statement is a hint to test for a property, never the property itself. Each pattern, its cue written as a property, and the alternative it is most often confused with:
| Pattern | Cue as a property | Nearest alternative | Why not |
|---|---|---|---|
| Fast and slow pointers | A linked list; a loop, the middle, or a position from the end | A hash set of nodes seen | It costs O(n) memory |
| Linked list reversal | A linked list reordered without a copy | Copying into an array | It costs O(n) memory |
| Tree patterns | A tree; the answer comes from above, below or the level | Copying the tree into a list | It loses the parent and child links |
| Grid traversal | A map of cells; movement between cells that touch | Building a graph first | The grid already gives the neighbours |
| Graph modelling | Links in pairs that nobody drew | A search of the list | It cannot follow links |
| Intervals | Items with a start and an end; overlaps or gaps | One slot per time unit | Its size follows the range, not the items |
| Heap patterns | The k best from anywhere, or a running middle | Sorting everything | It needs every item first, O(n log n) |
| Modified binary search | A yes-or-no test that changes once | Checking every candidate | It is O(n) tests |
| Monotonic stack | For each item, the nearest larger or smaller on one side | Scanning from each item | It is O(n²) |
| Sliding window | A contiguous run; fixed length, or a condition that moves one way | Heap patterns | A heap takes items that need not touch |
| Prefix sums | Range sums with negative values, or many questions of fixed data | Sliding window | Negative values break the window |
| Two pointers | Sorted input; pairs or a split | Binary search per element | It is O(n log n) and answers a single point |
| Bit manipulation | Small sets of flags, or constant memory for a single value | Hash map patterns | A map costs O(n) memory |
| Hash map patterns | Single items in unsorted input; memory allowed | Every pair | It is O(n²) |
Test structure first because it rules out the most patterns, and when no property fits, write the brute force and cost it: the step that dominates usually names the pattern that removes its waste.
← → move through sections and cards