Problem-Solving Patterns
Recurring techniques that crack interview and competitive-programming problems.
This is an overview — pick a sub-topic below.
Sub-topics (18)
Hashing Patterns
Use hash maps for counting, complement lookups and grouping.
Monotonic Stack
A stack kept in increasing or decreasing order to find next greater/smaller elements in $O(n)$.
Monotonic Queue
A deque kept in order to report a sliding-window maximum/minimum in $O(n)$ total.
Interval Problems
Merge, insert or schedule intervals — usually after sorting by start or end.
Binary Search on the Answer
Binary search over possible answers when feasibility is monotonic.
Meet in the Middle
Split a search into two halves of size $n/2$, enumerate each, then combine — $O(2^{n/2})$ instead of $O(2^n)$.
Coordinate Compression
Map large or sparse values to ranks $0..k-1$ so arrays and Fenwick trees can index them.
Top-K Problems
Find the $k$ largest/most frequent items with a size-$k$ heap in $O(n\log k)$, or quickselect in $O(n)$ average.
Reservoir Sampling
Pick $k$ random items uniformly from a stream of unknown length using $O(k)$ memory.
Randomized Algorithms
Use randomness for simplicity or expected speed: randomized quicksort, hashing, Monte Carlo methods.
Offline Queries
Read all queries first, reorder them (e.g. Mo's algorithm, sorting by endpoint), then answer.
Sweep Line Pattern
Convert intervals into start/end events, sort them, and sweep while tracking counts.
Game Theory
Determine winners of two-player games with optimal play.
Bitmask DP
DP over subsets encoded as bits — $O(2^n \cdot n)$ states.
Tree DP
DP computed bottom-up over a tree (children before parents).
Digit DP
Count numbers up to $N$ with digit properties by processing digits left to right with a "tight" flag.
Shortest Path Patterns
Choose the right algorithm for the graph: BFS (unweighted), 0-1 BFS (weights 0/1), Dijkstra (non-negative), Bellman-Ford (negative), Floyd-Warshall (all pairs), DAG DP.
Competitive Programming
Solve algorithmic problems fast and correctly under time limits.
Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.
Discussion (0)
Sign in or join free to ask questions and discuss this topic.