Coding Drills ยท 10

Backtracking & Design

The last six drills. Three generate every valid answer by walking a decision tree and undoing each choice on the way back up; three build small data structures whose every operation must run in O(1) or O(log k). Both halves reward the same habit: state an invariant first, then write the code that preserves it.

6
Drills
0
Easy
6
Medium
0
Hard
01 Arrays & Hashing ยท 02 Two Pointers ยท 03 Strings & Sliding Window ยท 04 Binary Search & Intervals ยท 05 Linked Lists ยท 06 Binary Trees & BST ยท 07 Grids & Matrices ยท 08 Graphs ยท 09 Dynamic Programming ยท 10 Backtracking & Design
01
Chapter One ยท Core Idea

Search Trees and Invariant-Driven Design

choose 1 choose 2 +2 +1 [ ] [1] [2] [1,2] [2,1] undo choose โ†’ explore โ†’ un-choose: one path array, reused

Backtracking is depth-first search over a tree of partial solutions. Each node is a partial answer (a prefix of a permutation, a partial sum, a half-built string); each edge is one choice. The algorithm walks down by choosing, records a result at a leaf, and walks back up by un-choosing โ€” restoring the shared state exactly as it was so the next sibling starts clean. Because one mutable path is reused for the whole search, memory is only O(depth) even when the tree has n! leaves. The running time is bounded by the size of the tree, which is why pruning โ€” refusing to enter a branch that cannot lead to a valid answer โ€” is the main optimisation.

The second half of the page is data-structure design: Min Stack, LRU Cache and a top-k heap. These are not search problems, but they share the mindset. You decide what invariant the structure maintains ("every entry knows the minimum beneath it", "the list is ordered by recency", "the heap holds the k best so far"), and every operation does a constant amount of work to keep it true. When a single built-in structure cannot give O(1) for all operations, you compose two of them.

Analogy: Backtracking is exploring a maze with a ball of string. At each junction you pick a corridor and unroll string; at a dead end or an exit you note what you found, then wind the string back to the last junction and try the next corridor. The string is the path list; winding it back is the un-choose step; walls you can see from the junction (and therefore never walk into) are pruning.
Counting the work in a backtracking search:
  • Leaves ร— cost per leaf: permutations have n! leaves and copying each costs O(n) โ†’ O(n ยท n!).
  • Branchingdepth: a combination search with branching b and depth d is O(bd) before pruning.
  • Output-sensitive bounds: Generate Parentheses produces Catalan(n) โ‰ˆ 4n/(n1.5โˆšฯ€) strings โ€” you cannot beat the output size.
02
Chapter Two ยท Mental Model

Which Tool Fits the Question

The question says "return ALL" permutations / combinations / strings
โ–ถ
The output itself can be exponential, so an exponential search is acceptable โ€” backtracking, not DP.
Every partial answer can be extended by a small set of choices
โ–ถ
Model it as a tree: node = partial answer, edge = one choice, leaf = complete answer.
One mutable path list / StringBuilder is shared by all recursive calls
โ–ถ
Every change made before a recursive call must be undone right after it โ€” or siblings inherit garbage.
A partial answer can already be judged hopeless (sum too big, too many ")")
โ–ถ
Prune before recursing: the whole subtree disappears, often turning "too slow" into "instant".
A design question lists operations with required complexities
โ–ถ
Pick the invariant that makes the hardest operation trivial, then make the other operations maintain it.
No single structure gives O(1) for every required operation
โ–ถ
Compose: HashMap for lookup + linked list for order (LRU); value + snapshot per entry (Min Stack).

Use the flow below to pick the technique from the problem statement. The first three rows are search problems that differ only in how the next choices are generated; the last three are design problems that differ in the invariant being maintained.

Output EVERY arrangement, where order matters? yes Backtracking + used[] drill 95 Permutations no Output every combination, order irrelevant? yes Backtracking + start index drill 96 Combination Sum no Build strings under a validity rule? yes Constrained construction drill 97 Generate Parentheses no Normal stack ops plus O(1) "current minimum"? yes Snapshot per entry drill 98 Min Stack no O(1) lookup AND O(1) "least recently used"? yes HashMap + doubly linked list drill 99 LRU Cache no Keep only the k best of n items / a stream? yes Bounded max-heap of size k drill 100 K Closest None of these and you only need a count or an optimum? โ†’ it is DP (page 09), not backtracking.
03
Chapter Three ยท Pattern Toolkit

Four Reusable Templates

Four templates: two for search (how to enumerate choices without duplicates) and two for design (how to make every operation cheap).

Template A โ€” Choose, explore, un-choose
The skeleton behind every backtracking drill. Only choices, valid and isComplete change between problems.
Pseudocode โ€” Template A (the backtracking skeleton)
function backtrack(state, path, result): if isComplete(path): result.add(copy(path)) // copy! path keeps changing return for each choice in choices(state): if not valid(choice): continue // pruning apply(choice) // choose backtrack(state, path, result) // explore undo(choice) // un-choose
Template A โ€” choose, explore, un-choose
The single path list over time (permutations of [1, 2, 3], first 11 events) start 1 choose 1 1 2 choose 2 1 2 3 choose 3 1 2 3 record 1 2 undo 1 undo 1 3 choose 3 1 3 2 choose 2 1 3 2 record 1 3 undo Every "choose" pushes; every return pops ("undo"). A leaf copies the path into the result (green) โ€” the list itself is reused.
Template B โ€” Start index & sorted pruning
For combinations, each level only looks at candidates from start onward, so the same multiset is never produced in two orders. Sorting first lets a single break discard every remaining candidate.
Pseudocode โ€” Template B (combinations with reuse)
function combine(cand (sorted), remaining, start, path): if remaining == 0: record(path); return for i = start to cand.length - 1: if cand[i] > remaining: break // sorted: the rest are bigger too path.add(cand[i]) combine(cand, remaining - cand[i], i, path) // i: reuse allowed; i+1: use once path.removeLast()
Template B โ€” start index and sorted pruning
Inside backtrack(remaining = 3, start = 1) while building [2, 2, ...] for target 7 2 i=0 before start 3 i=1 try: 3 โ‰ค 3 6 i=2 break: 6 > 3 7 i=3 never examined start sorted cand start index โ†’ no [3,2] after [2,3] recurse with i (not i+1) โ†’ the same number may repeat sorted + break โ†’ whole tail pruned in one comparison
Template C โ€” Augment or compose
Two ways to add a cheap query to a structure: store a snapshot of the answer in every entry (Min Stack), or pair a lookup structure with an ordering structure that point at the same nodes (LRU Cache).
Pseudocode โ€” Template C (compose for O(1))
// augment: store the answer to the extra query inside each entry push(x): stack.push( (x, min(x, stack.top.min)) ) getMin(): return stack.top.min // compose: a map finds the node, a doubly linked list orders the nodes get(k): node = map[k]; moveToFront(node); return node.value put(k,v): if full: map.remove(list.removeLast().key) node = new Node(k, v); map[k] = node; list.addFirst(node)
Template C โ€” compose structures to get O(1) for every operation
AUGMENT EACH ENTRY INDEX + ORDER val -3 min -3 val 0 min -2 val -2 min -2 โ† top answer the extra query from the top entry alone: O(1), survives pops key 3 key 1 key 2 MRU LRU 3=30 1=10 2=20 map finds the node in O(1); the list moves it in O(1)
Template D โ€” Bounded heap for top-k
Keep a heap of at most k items whose root is the item you would throw away next. Each of the n items costs O(log k), and memory stays O(k) โ€” ideal for streams.
Pseudocode โ€” Template D (bounded heap)
function kSmallest(items, k): heap = maxHeap() // root = worst of the kept items for each x in items: heap.offer(x) if heap.size > k: heap.poll() // evict the current worst return heap // the k smallest, O(n log k)
Template D โ€” bounded heap for top-k
k = 3 smallest distances; heap root = largest of the kept three 9 4 7 root = worst kept next = 12 12 > root 9 โ†’ ignore (offer, then poll it back out) next = 5 5 < root 9 โ†’ offer 5, size 4 > k โ†’ poll 9 result heap {4, 5, 7}: root is now 7 Max-heap for the k SMALLEST, min-heap for the k LARGEST: the root is always the next one to throw away. O(n log k).
04
Chapter Four ยท Drill 95

Permutations โ€” Ordered Choices

Drill 95 ยท Permutations
Mediumbacktracking + used[]LeetCode 46 โ†—
Given an array nums of distinct integers, return all possible permutations, in any order.
Example
Input: nums = [1, 2, 3] Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Key insight: Fill the positions left to right. Position 0 can take any of n numbers, position 1 any of the remaining n-1, and so on. A boolean[] used answers "is this number already placed?" in O(1), and un-marking it on the way back up frees it for the sibling branches.
From brute force to optimal

There is no way around generating n! outputs, so the goal is to avoid extra waste: no duplicate permutations, no re-scanning the path to see what is used, and no new list per call. The original drill used the in-place swap variant (swap nums[start] with each nums[i], recurse on start+1, swap back). It is also correct and needs no used array, but its output order is not lexicographic โ€” its comment claimed the last two results were [3,1,2], [3,2,1] while it actually produces [3,2,1], [3,1,2]. The used[] version below emits permutations in lexicographic order for sorted input and generalises to Permutations II (duplicates).

Walkthrough
Drill 95 โ€” full recursion tree for [1, 2, 3]
[ ] +1 [1] +2 [1,2] +3 [1,2,3] #1 +3 [1,3] +2 [1,3,2] #2 +2 [2] +1 [2,1] +3 [2,1,3] #3 +3 [2,3] +1 [2,3,1] #4 +3 [3] +1 [3,1] +2 [3,1,2] #5 +2 [3,2] +1 [3,2,1] #6 Level d fixes position d. used[] removes taken numbers, so level d has n - d branches: 3 x 2 x 1 = 6 leaves = n!. Leaves are produced left to right in exactly this order (#1 ... #6), matching the program output.
Java โ€” Permutations.java (complete, runnable)
import java.util.ArrayList; import java.util.List; public class Permutations { public static List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); backtrack(nums, new boolean[nums.length], new ArrayList<>(), result); return result; } private static void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) { if (path.size() == nums.length) { // a full arrangement result.add(new ArrayList<>(path)); // copy: path keeps changing return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; // already in this arrangement used[i] = true; // choose path.add(nums[i]); backtrack(nums, used, path, result); // explore path.remove(path.size() - 1); // un-choose used[i] = false; } } public static void main(String[] args) { System.out.println(permute(new int[]{1, 2, 3})); // [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] } }
Complexity
ApproachTimeSpaceNotes
Generate all nn sequences, filterO(nn ยท n)O(n)Wasteful: most sequences repeat a number
Swap-in-place backtrackingO(n ยท n!)O(n) stackOriginal drill; non-lexicographic order
used[] backtrackingO(n ยท n!)O(n) + outputLexicographic for sorted input
Common bugs & edge cases
  • result.add(path) without copying stores the same list n! times โ€” every entry ends up empty after the final un-choose.
  • Forgetting used[i] = false after the recursive call: only the first permutation is ever produced.
  • path.remove(path.size() - 1) is index-based; path.remove(Integer.valueOf(x)) also works, but path.remove(x) with an int x removes by INDEX.
  • With duplicates (Permutations II): sort, then skip i when nums[i] == nums[i-1] && !used[i-1].
05
Chapter Five ยท Drill 96

Combination Sum โ€” Unordered Choices with Reuse

Drill 96 ยท Combination Sum
Mediumbacktracking + start indexLeetCode 39 โ†—
Given distinct positive integers candidates and a target, return all unique combinations whose numbers sum to target. The same number may be chosen any number of times; combinations differing only in order count once.
Example
Input: candidates = [2, 3, 6, 7], target = 7 Output: [[2, 2, 3], [7]] Input: candidates = [2, 3, 5], target = 8 Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
Key insight: Make the combination non-decreasing in candidate index: after choosing candidate i, the next choice must be index i or later. Every multiset then has exactly one non-decreasing spelling, so [2,2,3], [2,3,2] and [3,2,2] collapse into one path โ€” no deduplication set needed.
From brute force to optimal

Without the start index the tree contains every ordering and you would need a Set of sorted lists to remove duplicates โ€” exponentially more work. Passing i (not i + 1) to the recursive call is what allows reuse. The original drill did not sort, so it could only skip a too-large candidate and still looped over the rest; sorting a copy and using break cuts all larger candidates in one comparison. The search tree for the example has just ten nodes:

Walkthrough
Drill 96 โ€” every node explored for candidates [2, 3, 6, 7], target 7
+2 +3 +6 +7 +2 +3 +3 +2 +3 [ ] rem 7 [2] rem 5 [3] rem 4 [6] rem 1 [7] rem 0 [2,2] rem 3 [2,3] rem 2 [3,3] rem 1 [2,2,2] rem 1 [2,2,3] rem 0 next 6 > 1: break next 3 > 2: break next 3 > 1: break next 2 > 1: break found #2 found #1 Children start at the parent's index: [3] never tries 2, so [3,2,2] cannot duplicate [2,2,3]. Red = dead ends cut by the sorted break.
Java โ€” CombinationSum.java (complete, runnable)
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class CombinationSum { public static List<List<Integer>> combinationSum(int[] candidates, int target) { int[] sorted = candidates.clone(); Arrays.sort(sorted); // enables the early break below List<List<Integer>> result = new ArrayList<>(); backtrack(sorted, target, 0, new ArrayList<>(), result); return result; } private static void backtrack(int[] cand, int remaining, int start, List<Integer> path, List<List<Integer>> result) { if (remaining == 0) { result.add(new ArrayList<>(path)); return; } for (int i = start; i < cand.length; i++) { if (cand[i] > remaining) break; // sorted: every later one is too big path.add(cand[i]); backtrack(cand, remaining - cand[i], i, path, result); // i, not i + 1: reuse allowed path.remove(path.size() - 1); } } public static void main(String[] args) { System.out.println(combinationSum(new int[]{2, 3, 6, 7}, 7)); // [[2, 2, 3], [7]] System.out.println(combinationSum(new int[]{2, 3, 5}, 8)); // [[2, 2, 2, 2], [2, 3, 3], [3, 5]] } }
Complexity
ApproachTimeSpaceNotes
All orderings + Set dedupExponential ร— orderingsLargeGenerates each multiset many times
Start index, no sortO(nT/m + 1)O(T/m)T = target, m = smallest candidate
Start index + sort + breakO(nT/m + 1) worstO(T/m)Same bound, far fewer nodes in practice
Common bugs & edge cases
  • The original stated O(2n) time; because candidates repeat, the depth is up to T/m, giving O(nT/m + 1) in the worst case.
  • Recursing with i + 1 forbids reuse (that is Combination Sum II); recursing with 0 re-creates every ordering.
  • Sorting the caller's array in place is a side effect โ€” the fixed code sorts a clone.
  • Combination Sum II (each number once, input has duplicates): recurse with i + 1 and skip i > start && c[i] == c[i-1].
06
Chapter Six ยท Drill 97

Generate Parentheses โ€” Build Only Valid Prefixes

Drill 97 ยท Generate Parentheses
Mediumconstrained constructionLeetCode 22 โ†—
Given n pairs of parentheses, generate all combinations of well-formed (balanced) parentheses.
Example
Input: n = 3 Output: ["((()))", "(()())", "(())()", "()(())", "()()()"] Input: n = 1 Output: ["()"]
Key insight: A prefix can still be completed to a valid string exactly when open โ‰ค n and close โ‰ค open. So add "(" while open < n, and add ")" only while close < open. Every leaf at length 2n is then automatically valid โ€” no final check.
From brute force to optimal

Brute force builds all 22n strings of "(" and ")" and validates each in O(n). The constrained version never creates an invalid prefix, so the work is proportional to the number of valid strings, the Catalan number C(n) (5 for n = 3, 16796 for n = 10). The original drill concatenated curr + "(", allocating a new String at every node; a single StringBuilder with append / deleteCharAt is the idiomatic choose / un-choose.

Walkthrough
Drill 97 โ€” generation tree for n = 2 (pruned branches in red)
+( +( +) +) +( +) +) "" "(" "((" "()" "(()" "()(" "(())" "()()" ")" close 0 < open 0? no "(((" open 2 < n 2? no "())" close 1 < open 1? no valid #1 valid #2 Red branches are never entered: the two counters reject them before recursing, so no invalid string is ever built.
nCatalan C(n) = resultsAll 22n strings
114
2216
3564
414256
8143065536
Java โ€” GenerateParentheses.java (complete, runnable)
import java.util.ArrayList; import java.util.List; public class GenerateParentheses { public static List<String> generateParenthesis(int n) { List<String> result = new ArrayList<>(); backtrack(new StringBuilder(), 0, 0, n, result); return result; } private static void backtrack(StringBuilder sb, int open, int close, int n, List<String> result) { if (sb.length() == 2 * n) { result.add(sb.toString()); return; } if (open < n) { // still have '(' to place sb.append('('); backtrack(sb, open + 1, close, n, result); sb.deleteCharAt(sb.length() - 1); } if (close < open) { // a ')' has something to match sb.append(')'); backtrack(sb, open, close + 1, n, result); sb.deleteCharAt(sb.length() - 1); } } public static void main(String[] args) { System.out.println(generateParenthesis(3)); // [((())), (()()), (())(), ()(()), ()()()] } }
Complexity
ApproachTimeSpaceNotes
All strings + validateO(22n ยท n)O(n)Mostly invalid strings
String concatenation backtrackingO(C(n) ยท n) plus copiesO(n2) live stringsOriginal drill
StringBuilder backtrackingO(C(n) ยท n) โ‰ˆ O(4n/โˆšn)O(n) + outputShown in the code
Common bugs & edge cases
  • Using close < n instead of close < open generates ")(" prefixes.
  • With a StringBuilder, forgetting deleteCharAt after the first branch leaks a "(" into the ")" branch.
  • Checking validity only at the leaves is correct but exponentially slower โ€” prune at every step.
  • The order of the two branches decides the output order; "(" first gives the lexicographic order shown.
07
Chapter Seven ยท Drill 98

Min Stack โ€” Remember the Answer at Push Time

Drill 98 ยท Min Stack
Mediumdesign: augmented entriesLeetCode 155 โ†—
Design a stack that supports push, pop, top and getMin (retrieve the minimum element), each in O(1) time.
Example
Calls: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin() Returns: -, -, -, -3, -, 0, -2
Key insight: A stack only ever changes at the top, so the minimum of the elements below an entry never changes while that entry exists. Store it next to the entry at push time: (value, min so far). Popping restores the previous minimum for free, because it is already in the new top.
From brute force to optimal

Scanning the stack in getMin is O(n). Keeping a single min variable fails on pop โ€” after removing the minimum you do not know the next one. The snapshot-per-entry design makes every operation O(1). The original drill used the classic two-stack variant (push onto the min stack when val <= minStack.peek()) on the legacy synchronized java.util.Stack; the version below uses ArrayDeque and one stack of pairs, which has no equality pitfalls.

Walkthrough
Drill 98 โ€” each entry carries the minimum at the time it was pushed
push(-2) -2 min -2 push(0) -2 min -2 0 min -2 push(-3) -2 min -2 0 min -2 -3 min -3 getMin() โ†’ -3 pop() -2 min -2 0 min -2 top() โ†’ 0, getMin() โ†’ -2 Popping -3 also pops its min snapshot โ€” the min below (-2) is already stored in the new top. Nothing is recomputed.
Java โ€” MinStack.java (complete, runnable)
import java.util.ArrayDeque; import java.util.Deque; public class MinStack { // each entry stores {value, minimum of the stack at the moment it was pushed} private final Deque<int[]> stack = new ArrayDeque<>(); public void push(int val) { int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]); stack.push(new int[]{val, min}); } public void pop() { stack.pop(); } public int top() { return stack.peek()[0]; } public int getMin() { return stack.peek()[1]; } public static void main(String[] args) { MinStack s = new MinStack(); s.push(-2); s.push(0); s.push(-3); System.out.println(s.getMin()); // -3 s.pop(); System.out.println(s.top()); // 0 System.out.println(s.getMin()); // -2 } }
Complexity
ApproachTimeSpaceNotes
Scan on getMinO(n) getMinO(n)Other ops O(1)
Two stacks (value + min)O(1) allO(n)Min stack only grows on new minimum or tie
Pairs (value, min)O(1) allO(n)Simplest invariant; shown in the code
Common bugs & edge cases
  • Two-stack variant with Deque<Integer>: stack.pop() == minStack.peek() compares references โ€” false for values outside -128..127. Use .equals or unbox to int first.
  • Two-stack variant: pushing onto the min stack only when val < min (strict) breaks on duplicate minima โ€” pop removes the min too early.
  • Prefer ArrayDeque over java.util.Stack, which extends the synchronized Vector.
  • LeetCode guarantees pop/top/getMin are never called on an empty stack; in production, throw NoSuchElementException explicitly.
08
Chapter Eight ยท Drill 99

LRU Cache โ€” Compose a Map and a List

Drill 99 ยท LRU Cache
Mediumdesign: HashMap + doubly linked listLeetCode 146 โ†—
Design a Least Recently Used cache with a fixed capacity. get(key) returns the value or -1; put(key, value) inserts or updates, and when the cache is full it first evicts the least recently used key. Both must run in O(1) average time.
Example
Input: capacity = 2 Calls: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4) Returns: -, -, 1, -, -1, -, -1, 3, 4
Key insight: Two requirements, two structures. A HashMap<key, Node> gives O(1) lookup. A doubly linked list kept in recency order gives O(1) "move to front" and "remove from back" โ€” but only because the map hands us the node directly, so we never search the list. Sentinel head and tail nodes remove every null check.
From brute force to optimal

An array or singly linked list needs O(n) to find and move an entry; a TreeMap keyed by timestamp gives O(log n). The map + doubly-linked-list composition is O(1) for both operations. Each node stores its key so that when the tail node is evicted we can also delete it from the map. A get counts as a use and moves the node to the front.

Walkthrough
Drill 99 โ€” LRU cache, capacity 2, LeetCode example sequence
operation list after the operation: MRU (head side) โ†’ LRU (tail side) result put(1,1) head 1=1 tail put(2,2) head 2=2 1=1 tail get(1) head 1=1 2=2 tail returns 1 put(3,3) head 3=3 1=1 tail evicts key 2 get(2) head 3=3 1=1 tail returns -1 (miss) put(4,4) head 4=4 3=3 tail evicts key 1 get(1) head 4=4 3=3 tail returns -1 (miss) get(3) head 3=3 4=4 tail returns 3 get(4) head 4=4 3=3 tail returns 4 Green = most recently used (just touched). Red = next eviction victim once the cache is full (capacity 2).
Java โ€” LRUCache.java (complete, runnable)
import java.util.HashMap; import java.util.Map; public class LRUCache { private static class Node { int key, value; Node prev, next; Node(int key, int value) { this.key = key; this.value = value; } } private final int capacity; private final Map<Integer, Node> map = new HashMap<>(); private final Node head = new Node(0, 0); // sentinel: most recent side private final Node tail = new Node(0, 0); // sentinel: least recent side public LRUCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; } public int get(int key) { Node node = map.get(key); if (node == null) return -1; moveToFront(node); // a read counts as a use return node.value; } public void put(int key, int value) { Node node = map.get(key); if (node != null) { // update existing key node.value = value; moveToFront(node); return; } if (map.size() == capacity) { // evict before inserting Node lru = tail.prev; unlink(lru); map.remove(lru.key); // why Node stores its key } node = new Node(key, value); map.put(key, node); addFront(node); } private void addFront(Node node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void unlink(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToFront(Node node) { unlink(node); addFront(node); } public static void main(String[] args) { LRUCache cache = new LRUCache(2); cache.put(1, 1); cache.put(2, 2); System.out.println(cache.get(1)); // 1 (order: 1, 2) cache.put(3, 3); // evicts 2 (order: 3, 1) System.out.println(cache.get(2)); // -1 cache.put(4, 4); // evicts 1 (order: 4, 3) System.out.println(cache.get(1)); // -1 System.out.println(cache.get(3)); // 3 System.out.println(cache.get(4)); // 4 } }
Java โ€” the LinkedHashMap shortcut (know it, but be ready to build the real one)
import java.util.LinkedHashMap; import java.util.Map; class LRUCacheLHM extends LinkedHashMap<Integer, Integer> { private final int capacity; LRUCacheLHM(int capacity) { super(capacity, 0.75f, true); // true = access order, not insertion order this.capacity = capacity; } public int get(int key) { return getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; // evict after inserting the new entry } }
Complexity
ApproachTimeSpaceNotes
Array / list scanO(n) per opO(capacity)Find + shift on every access
TreeMap by timestampO(log n) per opO(capacity)Two maps to keep in sync
HashMap + doubly linked listO(1) per opO(capacity)Shown in the code; LinkedHashMap does the same internally
Common bugs & edge cases
  • Not storing the key in the node: on eviction you cannot remove the entry from the map.
  • Forgetting that get must also move the node to the front โ€” then eviction removes a recently read key.
  • Updating an existing key without moving it to the front, or evicting on an update when the cache is full (size does not grow).
  • Pointer order in addFront: set the new node's prev/next first, then head.next.prev, then head.next โ€” reversing the last two loses the old first node.
09
Chapter Nine ยท Drill 100

K Closest Points โ€” Bounded Heap

Drill 100 ยท K Closest Points to Origin
Mediumbounded max-heapLeetCode 973 โ†—
Given points [x, y] on a plane and an integer k, return the k points closest to the origin (Euclidean distance). The answer may be in any order.
Example
Input: points = [[3, 3], [5, -1], [-2, 4]], k = 2 Output: [[3, 3], [-2, 4]] Input: points = [[1, 3], [-2, 2]], k = 1 Output: [[-2, 2]]
Key insight: Keep the k best candidates in a max-heap. Its root is the worst of the kept points, which is exactly the one to discard when a closer point arrives. Comparing squared distances (xยฒ + yยฒ) avoids Math.sqrt and floating-point error โ€” the order is the same.
From brute force to optimal

Sorting all points by distance is O(n log n). A size-k max-heap is O(n log k) and O(k) memory, and also works on a stream where n is unknown. Quickselect is O(n) on average but O(n2) worst case and reorders the input. The original drill claimed the output order was closest-first, but polling a max-heap returns the farthest first โ€” the fixed version fills the result from the back.

Walkthrough
Drill 100 โ€” k = 2 closest of [[3,3], [5,-1], [-2,4]]
(0,0) (3,3) d=18 (5,-1) d=26 (-2,4) d=20 dashed circle: radius โˆš20 = the k-th smallest distance max-heap trace (root = farthest kept) offer (3,3) d=18 heap = [18] offer (5,-1) d=26 heap = [26, 18] offer (-2,4) d=20 size 3 > k โ†’ poll farthest (5,-1) (d=26) heap = [20, 18] result: (3,3) and (-2,4)
Java โ€” KClosestPoints.java (complete, runnable)
import java.util.Arrays; import java.util.PriorityQueue; public class KClosestPoints { private static int dist2(int[] p) { // squared distance: no sqrt needed return p[0] * p[0] + p[1] * p[1]; } public static int[][] kClosest(int[][] points, int k) { // max-heap on distance: the root is the farthest of the k kept so far PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(dist2(b), dist2(a))); for (int[] p : points) { heap.offer(p); if (heap.size() > k) heap.poll(); // drop the farthest } int[][] result = new int[heap.size()][]; for (int i = result.length - 1; i >= 0; i--) result[i] = heap.poll(); return result; // closest first } public static void main(String[] args) { int[][] points = {{3, 3}, {5, -1}, {-2, 4}}; System.out.println(Arrays.deepToString(kClosest(points, 2))); // [[3, 3], [-2, 4]] System.out.println(Arrays.deepToString( kClosest(new int[][]{{1, 3}, {-2, 2}}, 1))); // [[-2, 2]] } }
Complexity
ApproachTimeSpaceNotes
Sort by distanceO(n log n)O(n) or O(log n)Simplest; fine for small n
QuickselectO(n) average, O(n2) worstO(1) extraMutates input; result unordered
Max-heap of size kO(n log k)O(k)Streaming-friendly; shown in the code
Common bugs & edge cases
  • Using a min-heap of all n points and polling k times is O(n + k log n) โ€” fine, but it stores everything; the bounded max-heap is the "top-k" pattern interviewers look for.
  • The original used a subtraction comparator. It happens to be safe here (both squared distances are non-negative ints), but a - b overflows for mixed-sign values โ€” make Integer.compare the habit.
  • Comparing Math.sqrt doubles works but is slower and invites precision bugs. Squared distances are exact ints for |x|, |y| โ‰ค 104; beyond about 32,000 per coordinate switch dist2 to long.
  • Ties at the k-th distance: any choice is accepted; do not add tie-breaking logic unless asked.
10
Chapter Ten ยท Summary

All Six Drills at a Glance

The six drills split cleanly: three enumerate a search tree and differ only in how choices are generated (all unused items, items from a start index, characters allowed by two counters); three maintain an invariant that makes the expensive query free. Space for the search drills excludes the output itself.

#DrillPatternTimeSpaceLevel
95PermutationsBacktracking + used[]O(n ยท n!)O(n)Medium
96Combination SumBacktracking + start index + sorted breakO(nT/m+1)O(T/m)Medium
97Generate ParenthesesConstrained constructionO(4n/โˆšn)O(n)Medium
98Min StackEntry + min snapshotO(1) per opO(n)Medium
99LRU CacheHashMap + doubly linked listO(1) per opO(capacity)Medium
100K Closest Points to OriginBounded max-heapO(n log k)O(k)Medium
Patterns to carry forward:
  • Copy at the leaf, undo after the call โ€” the two lines that make a shared path safe.
  • Ordering kills duplicates โ€” a start index (or sorted skip rule) is cheaper than any dedup set.
  • Prune before you recurse โ€” reject a prefix as soon as it cannot lead to a valid answer.
  • Design = invariant + O(1) maintenance โ€” and compose structures when one is not enough.
What to practice next

โ† 09 ยท Dynamic Programming All drills 01 ยท Arrays & Hashing โ†บ