Algorithms from zero
Toolbox: technique-selection review
Crux Cross-track multiple choice: read each problem, then pick the technique and the reason, weighing complexity, data structure, and the failure mode of the wrong tool.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skyThe whole track collapses into one skill: read a problem and name the right tool before you write a line. Each question hands you a problem statement and asks not ‘what is the answer’ but ‘which technique, and why that one over the tempting wrong one’.
Goal
Confirm you can map a problem’s shape — its constraints, its structure, what it asks — onto the technique that fits, and explain why the obvious alternative fails or wastes time.
Quiz
Completed
You are given an unsorted array of 10^6 integers and must answer 10^5 queries of the form 'does value X exist?'. Which approach, and why?
Heads-up This works and is a fine fallback, but for pure membership a hash set answers in O(1) average versus O(log n), and you avoid the n log n sort. Binary search wins only when you also need order or range queries.
Heads-up O(n) per query times 10^5 queries is 10^11 operations. The whole point of the track is to spend O(n) preprocessing once to make each query cheap. This is the brute force the other tools exist to beat.
Heads-up Sorting does not help a membership query unless you then binary-search; a post-sort linear scan is still O(n) per query. You have paid for sorting and gained nothing.
Quiz
Completed
A problem asks for the number of distinct ways to make change for amount N using given coin denominations. N is up to 10^4. Which technique, and what is the tell?
Heads-up Greedy gives a valid solution for canonical coin systems but does NOT count all ways, and for arbitrary denominations it can even miss the minimum. Counting distinct combinations requires summing over subproblems — that is DP, not greedy.
Heads-up Backtracking explores the full combination tree — exponential in N. The subproblems overlap massively (the same remaining-amount recurs across branches), which is exactly the signal to memoise or tabulate. Pure backtracking times out.
Heads-up Binary search on the answer needs a monotonic feasibility predicate over a numeric range. Number of ways to make change is a counting problem with no such monotone structure to bisect.
Quiz
Completed
You must find the k smallest elements of a stream of n numbers (n unknown in advance, k fixed and small). Which data structure carries the technique?
Heads-up You cannot sort a stream of unknown length without buffering all n elements, costing O(n) memory and O(n log n) time. The heap keeps only k items and never sees all n at once.
Heads-up A min-heap of size k makes it cheap to pop the smallest, but to KEEP the k smallest you must cheaply evict the largest of your current k — that is the max at the root of a max-heap. A min-heap forces an O(k) scan to find the element to drop.
Heads-up A hash set gives membership, not order. It cannot tell you which element to evict to keep the k smallest. Order-by-priority is the heap's job.
Quiz
Completed
Given a sorted array, find two indices whose values sum to a target. The array can be huge and you must use O(1) extra space. Which technique?
Heads-up The hash-map two-sum is the right tool for an UNSORTED array, but it costs O(n) extra space. Here the array is already sorted and space is constrained — two pointers exploit the order for O(1) space. Reading the constraints picks the tool.
Heads-up O(n log n) and ignores the structure that the two-pointer sweep exploits. It works, but it is strictly slower than the O(n) two-pointer pass and the question asks you to use the sortedness fully.
Heads-up Enumerating all pairs is O(n^2) and throws away the sorted order entirely. Sorted input is the loudest possible hint for two pointers or binary search, never brute-force pair enumeration.
Quiz
Completed
You must detect whether a directed dependency graph has a cycle, and if not, produce a valid build order. Which technique?
Heads-up Dijkstra finds shortest weighted paths; it neither detects cycles in a dependency sense nor produces an ordering respecting all precedence constraints. Ordering by dependencies is topological sort, not shortest path.
Heads-up Union-Find detects cycles in UNDIRECTED graphs. Dependency graphs are directed, where a back-edge — not a shared component — signals a cycle, and you also need an ordering. Toposort delivers both.
Heads-up Subset DP is for problems like Hamiltonian paths or TSP on small graphs (exponential in V). Ordering by precedence is linear-time toposort; DP is wildly oversized here.
Quiz
Completed
A problem gives n <= 20 items and asks for the optimal subset under a constraint that resists any greedy or DP-by-value formulation. The constraints scream a particular family. Which, and what is the n <= 20 tell?
Heads-up Small n does not make a greedy correct — correctness is about structure (exchange argument or matroid), not size. The tell of n <= 20 is permission to enumerate exponentially, precisely because no polynomial greedy or DP fits.
Heads-up DP-by-value needs a bounded numeric dimension to tabulate over; the problem states it resists that formulation. When the natural state IS the subset and n is tiny, you enumerate subsets (2^n), not values.
Heads-up Constraint sizes are the primary signal for technique choice. n <= 20 (about 10^6 subsets) versus n <= 10^5 (needs O(n log n)) versus n <= 10^9 (needs O(log n) or math) each point at a different family. Ignoring n discards the loudest hint.
Recap
Technique selection is reading, not recall. Constraint sizes are the loudest signal: n ≤ 20 licenses 2^n enumeration; n ≤ 10^5 demands O(n log n); 10^9 forces O(log n) or math. The problem’s verb picks the family — does it exist maps to hashing; k smallest or next priority maps to a heap; ways to count or optimise over overlapping subproblems maps to DP; best local choice you can prove maps to greedy; order by dependency maps to toposort; pair in sorted data with O(1) space maps to two pointers. Every wrong answer above is a real tool misapplied — the skill is matching shape to tool, then knowing why the tempting alternative wastes time or breaks.