Practice Solutions Appendix

What & why: every practice / variation problem referenced anywhere in this book, in one place, with a compact Approach hint that gets you unstuck without spoiling the solve. Click through to LeetCode; jump to the corresponding pattern chapter for the full template.

How to use it

attempt each problem from its pattern card first. If you stall, read only the Approach cell (2–3 lines). The 40+ hardest variations have a full numbered-steps walkthrough below the tables.

316 practice / variation problems indexed across 31 pattern areas — this is the one place to check when you want a hint. For the full write-up on a canonical problem, use the Master Problem Index to jump straight to its section.

Sliding Window

Problem	Approach hint
Binary Subarrays With Sum	same trick, "sum = S" over a 0/1 array
Constrained Subsequence Sum	same windowed-max of a dp array, with the window being the allowed gap k
Count Number of Nice Subarrays	same trick, "K odd numbers" as the count
Diet Plan Performance	classify each window by sum thresholds; sum score
Find All Anagrams in a String · ⇩ walkthrough	slide a char-count vector; record left when it matches need[]
Frequency of the Most Frequent Element	sort, then window where windowLen·max − windowSum ≤ k operations
Fruits into Baskets · ⇩ walkthrough	it's literally "at most 2 distinct" dressed up as picking fruit into two baskets
Get Equal Substrings Within Budget	shrink when the total change-cost inside the window exceeds the budget
Jump Game VI	the deque holds the best dp value reachable within the jump range; front = best score to jump from
Longest Palindromic Substring	Adding a char at the right can turn a valid palindrome into an invalid one — but also into a larger valid one. Non-monotone.
Longest Repeating Character Replacement	the window is valid while windowLen − countOfMostFrequentChar ≤ K (you may replace up to K of the minority)
Longest Substring with exactly K distinct	Exactly-K validity isn't monotone: a window with 3 distinct isn't "valid" for K=2 nor for K=4.
Longest Substring with At Most K Distinct · ⇩ walkthrough	allow up to K different characters instead of zero repeats; shrink while the distinct-count exceeds K (track counts in a small map)
Longest Substring Without Repeating Characters	See the pattern chapter for the template.
Max Consecutive Ones III	over a 0/1 array, shrink only when the number of zeros in the window exceeds K (you may flip K zeros)
Maximum Average Subarray I	plain sum, divide by k at the end
Maximum Subarray	The "rule" here is "which subarray has max sum?" — there's no growing/shrinking validity, only a choice: keep extending or restart.
Minimum Size Subarray Sum	this exact shape (positive values, sum ≥ target)
Minimum Window Subsequence	the target must appear in order (not just as a multiset), so track progress through the pattern instead of counts
Minimum Window Substring	validity is "covers all required characters," tracked with a have/need counter
Number of Substrings Containing All Three Characters	count from the shrinking side: count += left at each valid right
Permutation in String · ⇩ walkthrough	same as above; return true on the first match
Replace the Substring for Balanced String	shrink while the outside-window counts are already balanced
Shortest Subarray with Sum ≥ K	Same reason — negatives break the shortest-variable shrink rule.
Subarray Product Less Than K	The product argument (product /= a[left] restores validity) assumes strictly-positive integers. Zeros make the product 0 permanently; negatives flip the inequality direction.
Subarray Sum Equals K	Adding a negative can lower the running sum below K after it was above → invalid can become valid again by growing. Extension test fails.
Substring with Concatenation of All Words	the "characters" are whole words of equal length
Trapping Rain Water	Water at each index depends on the max on both sides — not on a window that slides in one direction.

Two Pointers

Problem	Approach hint
3Sum Closest · ⇩ walkthrough	instead of hunting for exactly 0, track the sum closest to target as the pointers move
3Sum Smaller	count triplets with sum < target; when a[lo]+a[hi] < target, all hi−lo pairs qualify at once, so add them in one shot
4Sum · ⇩ walkthrough	add one more outer loop, then two-pointer the inner pair (skip duplicates at every level)
Boats to Save People	sort, then pair the lightest with the heaviest that still fits — a converging-pointer greedy
Container With Most Water	maximize a single span instead of summing trapped water; move the shorter wall
Intersection of Two Arrays II	sort both, then two pointers advancing the smaller side
Largest Rectangle in Histogram	the dual "peak" view — a monotonic stack finds how far each bar extends
Merge Sorted Array (in place, from the back)	fill from the largest end so you never overwrite unmerged values
Move Zeroes · ⇩ walkthrough	two categories (nonzero vs zero); a single write-pointer packs nonzeros to the front
Partition (Quicksort step)	the same in-place split around a pivot that powers Quickselect
Sort Array By Parity	partition into evens then odds with two pointers
Sort Colors	See the pattern chapter for the template.
Sort Transformed Array	after applying ax²+bx+c the extremes are at the ends (if a>0) or middle (if a<0); merge accordingly
Trapping Rain Water II (2D)	the "walls" are a whole grid boundary, so process cells outward from the lowest border using a min-heap
Valid Palindrome / Valid Palindrome II · ⇩ walkthrough	compare from both ends inward; II allows one mismatch (try skipping either side)
Wiggle Sort	partition around the median, then interleave the two halves

Fast / Slow Pointers

Problem	Approach hint
Find the Duplicate Number · ⇩ walkthrough	treat nums[i] as the next pointer and find the cycle entry
Happy Number	the "next" step is the sum of squared digits; a cycle means it's not happy
Linked List Cycle	stop as soon as fast meets slow (detection only)
Linked List Cycle II	See the pattern chapter for the template.
Middle of the Linked List	fast moves 2×, slow 1× → slow lands on the middle

Prefix Sum / Difference Array

Problem	Approach hint
2D — Range Addition II / stamping a grid	a 2D difference array marks the four corners of each rectangle
Car Pooling	a difference array over the timeline of pick-ups (+) and drop-offs (−); check capacity never overflows
Contiguous Array (equal 0s and 1s) · ⇩ walkthrough	treat 0 as −1; a subarray is balanced when two prefixes are equal
Continuous Subarray Sum (multiple of k)	same mod k bucketing, but store the earliest index to enforce a length ≥ 2
Corporate Flight Bookings	+seats at first, −seats after last; one sweep gives per-flight totals
Count Submatrices With Target Sum	fix a pair of rows, collapse columns to 1D prefix sums, then reuse the "subarray sum = k" hash-map count
Matrix Block Sum	answer each cell as the sum of a k-radius block using the same four-corner formula
Maximal Square / Maximal Rectangle	combine per-row prefix counts with a histogram/DP to bound the largest all-ones region
Range Addition · ⇩ walkthrough	the canonical form — apply many [l, r] += v in O(1) each, reconstruct once
Range Sum Query 2D	See the pattern chapter for the template.
Subarray Sums Divisible by K · ⇩ walkthrough	key the map on pre mod k instead of the raw prefix

Hashing (pattern)

Problem	Approach hint
3Sum	need three numbers summing to 0, no duplicate triplets
Candy · ⇩ walkthrough	each child must beat both neighbours
Find Duplicate File in System	same content
Group Anagrams	See the pattern chapter for the template.
Group Shifted Strings	same shift pattern ("abc"≡"bcd")
Isomorphic Strings	same structure ("egg"≡"add")
Longest Consecutive Sequence	1-D runs of integers
Maximum Product Subarray · ⇩ walkthrough	a negative flips sign
Number of Islands	2-D grid connectivity
Product of Array Except Self	See the pattern chapter for the template.
Two Sum	See the pattern chapter for the template.
Two Sum II — sorted input · ⇩ walkthrough	the array is already sorted
Two Sum III — design	numbers arrive over time, many find queries
Two Sum Less Than K	largest pair sum strictly < K
Valid Anagram · ⇩ walkthrough	two strings, not a whole group
Word Ladder · ⇩ walkthrough	words linked by 1-letter edits

Monotonic Stack

Problem	Approach hint
Daily Temperatures	See the pattern chapter for the template.
Next Greater Element II (circular)	iterate the array twice (i % n) so wrap-around neighbours are considered
Online Stock Span · ⇩ walkthrough	streaming version — push (price, span) and collapse spans of smaller prices as they arrive
Remove K Digits / Largest Rectangle variants	a monotonic stack that greedily pops to keep the sequence as small/large as possible
Sum of Subarray Minimums	each element contributes min × (countLeft × countRight); the monotonic stack gives those boundary counts

Binary Search

Problem	Approach hint
Find Minimum in Rotated Sorted Array	no target; steer toward the unsorted half, which is where the rotation point (the minimum) hides
Find Peak Element · ⇩ walkthrough	no sorted array at all — just move toward the larger neighbour; you're guaranteed to climb to a peak
Order-Agnostic Binary Search	first peek at the ends to detect ascending vs descending, then flip the comparison accordingly
Search in Rotated Array II (with duplicates)	when a[lo] == a[mid] == a[hi] you can't tell which half is sorted, so shrink both ends by one (worst case degrades to O(n))
Search in Rotated Sorted Array	See the pattern chapter for the template.

Binary Search on the Answer

Problem	Approach hint
Capacity to Ship Packages in D Days · ⇩ walkthrough	guess a ship capacity; feasibility = "can we finish in ≤ D days at this capacity?"
Divide Chocolate / Maximize the Minimum	flip it — maximize the smallest piece, so feasible(x) = "can make ≥ k pieces each ≥ x."
Find K-th Smallest Pair Distance	binary-search the distance; feasibility counts pairs within it via a sliding window
Koko Eating Bananas	guess a speed; feasibility = "finishes within H hours?"
Kth Element of Two Sorted Arrays	the general form — binary-search a partition so k elements sit on the left
Median of a Row-wise Sorted Matrix · ⇩ walkthrough	binary-search the value and count how many are ≤ mid
Minimize Max Distance to Gas Station	guess a distance; feasibility counts how many stations you'd have to add (works on real numbers, so fix an iteration count or epsilon)
Path With Minimum Effort	binary-search the max allowed step height; feasibility is a BFS/DFS connectivity check
Split Array Largest Sum / Book Allocation	guess a max segment sum; feasibility = "≤ m parts needed?"

Top-K / Heap

Problem	Approach hint
K Closest Points to Origin · ⇩ walkthrough	a max-heap of size k keyed on distance; the farthest of your current best sits on top, ready to be evicted
Kth Largest Element in a Stream	keep a size-k min-heap alive across add calls; its root is always the running kth largest
Top K Frequent Elements	heap keyed on frequency (or, for O(n), bucket by frequency and read the top buckets)

K-way Merge

Problem	Approach hint
Add Two Numbers	walk both lists together carrying a digit, building the result node by node
Merge k Sorted Lists	a min-heap of the k current heads yields the global next-smallest
Merge Two Sorted Lists	the base case — a dummy-head splice, no heap needed
Smallest Range Covering Elements from K Lists	the range spans the heap min and the running max of tops
Sort List	merge sort on a list — split by fast/slow, recurse, then merge two halves
Ugly Number II / Super Ugly Number	the streams are the sequence multiplied by each prime factor

Merge Intervals

Problem	Approach hint
Employee Free Time	merge everyone's busy intervals; the gaps between merged blocks are the free time
Insert Interval · ⇩ walkthrough	three phases — copy intervals before, merge those overlapping the new one, copy the rest
Interval List Intersections	two pointers; each overlap is [max(starts), min(ends)]
Merge Intervals	See the pattern chapter for the template.
Remove Covered Intervals	sort by start (then end desc) and count intervals not swallowed by a previous one

Sweep Line

Problem	Approach hint
Minimum Number of Platforms	peak of simultaneously-present trains
My Calendar II / III	a TreeMap of +1/−1 deltas; the max running prefix is the max overlap
The Skyline Problem	sweep x-coordinates with a max-heap of active building heights

Topological Sort

Problem	Approach hint
Alien Dictionary	build edges by comparing adjacent words' first differing character, then topo-sort the alphabet
Course Schedule II	emit the actual order, not just "is it possible?"
Minimum Height Trees	peel leaves layer by layer on an undirected tree; the last 1–2 remaining are the centroids
Parallel Courses	count the number of Kahn "waves" — that's the minimum number of semesters

Union-Find (DSU)

Problem	Approach hint
Accounts Merge	union accounts that share any email, then group emails by root
Connecting Cities With Minimum Cost	plain Kruskal on the given edge list; return −1 if it stays disconnected
Find Critical and Pseudo-Critical Edges	rerun MST forcing each edge in / leaving it out to classify it
Min Cost to Connect All Points	the graph is implicit — every pair of points is an edge weighted by Manhattan distance
Most Stones Removed	union stones sharing a row or column; removable = total − components
Number of Islands II	online — union each newly added land cell with its neighbours, tracking the component count
Number of Provinces · ⇩ walkthrough	union adjacent friends; the answer is the count of distinct roots
Optimize Water Distribution in a Village	model each well as an edge from a virtual node 0, then run MST
Redundant Connection	the answer is the first edge whose two endpoints are already connected

Greedy

Problem	Approach hint
Best Time to Buy and Sell Stock · ⇩ walkthrough	track the min price so far and the best profit against it
Course Schedule III	sort by deadline; greedily take courses, dropping the longest with a max-heap when you overrun
Gas Station	reset the start to i+1 when the tank dips below 0, with a global feasibility gate
Jump Game I	just track the farthest reachable index; return whether it reaches the end
Jump Game II	See the pattern chapter for the template.
Jump Game III	actual BFS/DFS since you can jump both directions by arr[i]
Maximum Length of Pair Chain	the same earliest-finish chain, counting length
Minimum Number of Arrows	the interval-cover cousin (sort by end)
Non-overlapping Intervals	removals = total − (max non-overlapping kept)
Task Scheduler	See the pattern chapter for the template.
Video Stitching / Minimum Number of Taps	the same "cover the line in fewest intervals" farthest-reach greedy

Recursion & Backtracking

Problem	Approach hint
Beautiful Arrangement	place numbers 1..n where position i must divide (or be divided by) the value
Combination Sum	See the pattern chapter for the template.
Combination Sum / Combination Sum II · ⇩ walkthrough	carry a remaining-target budget; allow reuse by recursing with the same i (unbounded) or forbid it with i+1 (each item once)
Combination Sum III	exactly k numbers drawn from 1..9 summing to n
Combination Sum IV	it counts ordered ways → drop backtracking for a 1-D DP (dp[t] += dp[t-num])
Letter Case Permutation	at each letter, branch into lower/upper case
Letter Combinations of a Phone Number	the "constraint" is just the digit→letters map; place one letter per position
N-Queens	See the pattern chapter for the template.
N-Queens II	just count the valid placements instead of listing boards
Next Permutation	in-place — find the pivot, swap with its next-larger suffix element, reverse the suffix
Palindrome Partitioning · ⇩ walkthrough	a "choice" is a prefix that happens to be a palindrome; recurse on the rest
Permutations	order matters, so drop the start index and instead track a used[] array, scanning all positions each level
Permutations II (with duplicates) · ⇩ walkthrough	sort, then skip i>0 && a[i]==a[i-1] && !used[i-1] to avoid duplicate orderings
Robot Room Cleaner	same visited-set DFS, but you only know relative moves (turn/forward)
Subsets II (with duplicates) · ⇩ walkthrough	sort first, then skip equal siblings (i > start && a[i] == a[i-1]) so you don't emit the same subset twice
Sudoku Solver	three occupancy sets (row, column, 3×3 box); place a digit, recurse, undo
Unique Paths III	backtrack across the grid, requiring you visit every empty cell exactly once
Valid Sudoku	no search at all — only check the occupancy sets for conflicts
Word Search	See the pattern chapter for the template.
Word Search II	many target words → back the grid DFS with a Trie so all words are pruned at once

Divide & Conquer

Problem	Approach hint
Count of Range Sum	run merge sort over the prefix sums, counting sums in [lower, upper]
Count of Smaller Numbers After Self	count how many right-half elements slot in before each left element
Reverse Pairs	before merging, count pairs with a[i] > 2·a[j]

Dynamic Programming

Problem	Approach hint
Best Time to Buy/Sell with Cooldown · ⇩ walkthrough	states hold / sold / rest; selling forces a rest day
Best Time with at most k Transactions	add a transaction-count dimension to the state
Best Time with Transaction Fee	subtract the fee on each sell transition
Climbing Stairs	dp[i] = dp[i-1] + dp[i-2] (count ways, no conflict)
Coin Change (min coins) · ⇩ walkthrough	unbounded items → loop capacity upward, take min(dp[w], dp[w-coin]+1)
Coin Change II (count ways)	dp[a] += dp[a−coin], with coins in the outer loop so each combination is counted once (order ignored)
Delete and Earn	bucket the array by value, then it's House Robber over value × count
Dungeon Game	fill the grid backwards from the goal, because required health propagates in reverse
Edit Distance · ⇩ walkthrough	mismatch costs 1 + min(insert, delete, replace)
House Robber	See the pattern chapter for the template.
House Robber II	houses in a circle → run the linear DP twice (exclude first, exclude last) and take the max
Last Stone Weight II	minimize `
Longest Common Subsequence	match → dp[i-1][j-1]+1, else max(dp[i-1][j], dp[i][j-1])
Longest Increasing Subsequence · ⇩ walkthrough	single sequence → patience sorting with binary search for
Longest Palindromic Subsequence	LCS of s and reverse(s)
Matrix Chain Multiplication	k is the last multiplication point; cost combines the two sub-products
Maximal Square	dp = min(up, left, up-left) + 1 for the largest all-ones square
Maximum Sum Circular Subarray	answer = max(normal Kadane, total − min-subarray)
Min Cost Climbing Stairs / Paint Fence	the same 1-D recurrence with a per-step cost or an adjacency constraint
Minimum Cost to Merge Stones	merge in groups of k; the split respects (len-1) % (k-1)
Minimum Path Sum / Minimum Falling Path Sum	min of the neighbours plus the cell
Number of Ways to Assign (hats/jobs)	iterate the mask of assigned people, adding one compatible assignment at a time
Paint House I/II	the state is the last colour used; the transition forbids repeating it
Palindrome Partitioning II	min cuts via an interval palindrome table
Partition Equal Subset Sum	target = sum/2; the boolean knapsack asks if it's reachable
Partition to K Equal Sum Subsets	track the used-element mask plus the current bucket's remaining capacity
Perfect Squares	the "coins" are the square numbers 1, 4, 9, 16, …; minimize the count
Regex / Wildcard Matching	the same grid, with * allowing "skip" or "repeat" transitions
Shortest Path Visiting All Nodes	BFS over (node, mask) states — shortest walk covering every node
Target Sum	assigning ± signs reduces to "subset summing to (sum+target)/2" → count instead of boolean
Travelling Salesman	dp[mask][i] = cheapest route visiting mask, ending at i
Unique Paths · ⇩ walkthrough	See the pattern chapter for the template.
Unique Paths / Unique Paths II	add the two neighbours to count paths (obstacles set the cell to 0)

Trie (pattern)

Problem	Approach hint
Concatenated Words	a trie of all words + DFS to test whether a word is built from shorter ones
Count Pairs With XOR in a Range	store subtree counts in the binary trie and count paths whose XOR falls in [low, high]
Maximum XOR of Two Numbers in an Array	See the pattern chapter for the template.
Maximum XOR With an Element From Array	answer queries offline, sorting by the value bound and inserting numbers as they become allowed
Replace Words / IP routing	the same MSB-first bit walk used for longest-prefix matching
Stream of Characters	store words reversed in a trie and match the incoming stream from the back

Bit Manipulation

Problem	Approach hint
Counting Bits · ⇩ walkthrough	See the pattern chapter for the template.
Find the Difference / Set Mismatch	XOR the two collections so shared characters cancel, leaving the odd one out
Hamming Distance	Integer.bitCount(a ^ b) — count differing bits
Maximum Product of Word Lengths	encode each word's letters as a 26-bit mask; two words share no letter iff maskA & maskB == 0
Missing Number · ⇩ walkthrough	XOR all indices 0..n with all values; the survivor is the missing one
Number of 1 Bits	Brian Kernighan's x &= x - 1 clears the lowest set bit each step
Power of Two	x > 0 && (x & (x-1)) == 0
Reverse Bits	shift bits out of one int and into another, one position at a time
Single Number	See the pattern chapter for the template.
Subsets	loop masks 0 .. 2ⁿ-1; bit i set means element i is included
Sum of All Subset XOR / SOS DP	enumerate submasks with for (s = m; s > 0; s = (s-1) & m)

Math & Number Theory

Problem	Approach hint
Count Primes	count marks left unmarked
Fraction to Recurring Decimal	track remainders to find the repeating cycle
GCD of Strings	GCD of lengths; verify s+t == t+s
Matrix exponentiation	base is a matrix → nth Fibonacci / linear recurrence
Pow(x, n)	real base, handle negative exponent
Super Pow	huge exponent as a digit array, mod 1337
Water and Jug Problem	feasible iff target % gcd(x,y) == 0 (Bézout)

Design & Randomized

Problem	Approach hint
Insert Delete GetRandom O(1)	map value→index + swap-with-last
Linked List Random Node	single reservoir of size 1
LRU Cache	map + doubly-linked list for recency
Random Pick Index	reservoir over indices matching a target
Random Pick with Weight · ⇩ walkthrough	prefix-sum array + binary search
Shuffle an Array · ⇩ walkthrough	Fisher–Yates: swap i with random ≤ i
… Duplicates allowed	map value→set of indices

Arrays (DS)

Problem	Approach hint
Find All Numbers Disappeared / Find All Duplicates · ⇩ walkthrough	scan for every wrong slot instead of the first
First Missing Positive	ignore values outside 1..n; the answer lies in 1..n+1
Rotate Image	transpose + reverse rows (90° CW)
Search a 2D Matrix · ⇩ walkthrough	treat the grid as one sorted array → binary search
Search a 2D Matrix II · ⇩ walkthrough	start top-right; go left on bigger, down on smaller
Set Matrix Zeroes	border-as-marker + col0 flag
Set Mismatch	the single wrong slot reveals both the duplicated and the missing number
Spiral Matrix	See the pattern chapter for the template.
Spiral Matrix II · ⇩ walkthrough	write 1..n² along the same spiral bounds

Strings

Problem	Approach hint
Encode and Decode Strings	See the pattern chapter for the template.
Encode/Decode TinyURL	map long↔short with a counter or base-62 id instead of embedding the payload
Palindromic Substrings	count every successful expansion instead of keeping only the longest
Serialize N-ary Tree	prefix each node with its child count so the parser knows when to stop
Serialize/Deserialize Binary Tree	pre-order with # null markers makes the traversal reversible
Shortest Palindrome	use the KMP failure function on s + '#' + reverse(s) to find the longest palindromic prefix

Linked Lists

Problem	Approach hint
All O`one Data Structure	buckets of equal-count keys threaded in a doubly linked list for O(1) min/max
Design Browser History	a doubly linked list of pages with back/forward pointers
LFU Cache	add frequency buckets (a map from frequency → ordered list) alongside the key map
Palindrome Linked List	reverse the second half and compare it against the first
Reorder List	reverse the second half, then interleave it with the first
Reverse Linked List	See the pattern chapter for the template.
Reverse Linked List II (sublist)	reverse only the nodes in [left, right], then stitch the ends back
Reverse Nodes in k-Group · ⇩ walkthrough	reverse each block of k and reconnect blocks (leave a trailing remainder as-is)
Rotate List	find the new tail k from the end, then relink into a rotation
Swap Nodes in Pairs	the k = 2 special case

Stacks & Queues

Problem	Approach hint
Basic Calculator I/II	push running values and signs; resolve on operators and closing brackets
Decode String	push (repeatCount, prefix) on [, pop and expand on ]
Longest Valid Parentheses	keep a stack of indices to measure the length of each valid span
Max Stack	track a running max per entry (or a second stack) for O(1) peekMax
Min Remove to Make Valid Parentheses	push indices of unmatched (; drop leftovers at the end
Min Stack	See the pattern chapter for the template.
Sliding Window Minimum/Maximum	the queue version — a monotonic deque holding candidate extremes
Valid Parentheses	See the pattern chapter for the template.

Trees

Problem	Approach hint
Average of Levels	sum ÷ count for each level
Balanced Binary Tree	return height, but short-circuit with -1 the moment a subtree is unbalanced
Binary Tree Cameras	return a 3-state (has-camera / covered / needs-cover) and place cameras greedily from the leaves up
Binary Tree Maximum Path Sum	return the best single branch, but update the global with left+node+right (clamp negative branches to 0)
Construct Binary Tree from Preorder and Inorder	See the pattern chapter for the template.
Construct BST from Preorder	no inorder needed — split children using value bounds
Construct from Inorder + Postorder	consume postorder from the back, building the right subtree before the left
Construct from Preorder + Postorder	works only for full trees; the second preorder value marks the left subtree's root
Construct String from Binary Tree	parenthesised encoding 1(2)(3) that stays reversible
Convert BST to Sorted Doubly Linked List	thread prev/next pointers as you visit in order
Convert Sorted Array/List to BST	the middle element is the root → balanced BST
Diameter of an N-ary Tree	combine the two largest child depths instead of left/right
Diameter of Binary Tree	See the pattern chapter for the template.
Distance Between Two Nodes	depth(p) + depth(q) − 2·depth(lca)
Distribute Coins in Binary Tree	return each subtree's surplus/deficit; sum `
Find Duplicate Subtrees	serialize every subtree to a string, hash them, and report repeats
House Robber III	return {rob, skip}; robbing a node forbids robbing its children
Kth Smallest in a BST · ⇩ walkthrough	do an in-order walk and stop after the kth node
LCA of a BST	use the ordering — descend left/right until the two targets split, no full search
LCA of Deepest Leaves	return (depth, node) upward and keep the node whose subtree holds the deepest leaves
LCA with Parent Pointers	walk up both ancestor chains and align lengths (like linked-list intersection)
Longest Univalue Path	extend a branch only through children with the same value
Longest ZigZag Path	return {leftLen, rightLen} and update a global maximum
Minimum Depth	return as soon as you hit the first leaf (BFS finds it earliest)
Range Sum of BST	prune whole subtrees that fall entirely outside [low, high]
Recover BST	the in-order sequence has exactly two out-of-order nodes; find and swap them
Right Side View · ⇩ walkthrough	keep the last node of each level
Serialize/Deserialize BST	no null markers needed — rebuild using value bounds since it's ordered
Validate Binary Search Tree	See the pattern chapter for the template.
Zigzag Level Order	reverse the collected list on alternate levels

Heaps (DS)

Problem	Approach hint
Find Median from Data Stream	the base case — balance the two heaps on every insert
IPO / Maximize Capital	a min-heap unlocks projects you can afford, a max-heap picks the most profitable of those
Sliding Window Median	add lazy deletion so the element leaving the window is discarded from whichever heap holds it

Tries

Problem	Approach hint
Add and Search Word (wildcard .)	on a ., recurse into all children at that position (DFS instead of a single step)
Implement Trie (Prefix Tree)	See the pattern chapter for the template.
Longest Word in Dictionary	accept a word only if every one of its prefixes is also a stored word
Map Sum Pairs	store a value at each terminal and sum the values in the subtree under a prefix

Graphs

Problem	Approach hint
01 Matrix	sources are all the 0-cells; each 1-cell gets its distance to the nearest 0
All-pairs, small V	switch to Floyd–Warshall — dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
As Far From Land as Possible	sources are all land cells; the answer is the last water cell reached (max distance)
Cheapest Flights Within K Stops	add a stop-budget dimension, or run Bellman–Ford for exactly K+1 rounds
Clone Graph	a Map<Node,Node> original→copy doubles as the visited set; wire neighbours on first visit
Course Schedule (cycle detect)	the map stores a 3-colour state (unvisited / in-progress / done) to catch back-edges
Cracking the Safe	Eulerian circuit on a de Bruijn graph
Critical Connections · ⇩ walkthrough	bridge test low[v] > disc[u]
Evaluate Division	a weighted DFS where the map carries the running product along the path
Is Graph Bipartite / Possible Bipartition	the map stores a 2-colouring; a same-colour neighbour means an odd cycle
Max Area of Island	have the flood return the cells it sank, and keep the maximum instead of a count
Negative-cycle detection	run the extra V-th pass; a relaxation ⇒ cycle
Network Delay Time · ⇩ walkthrough	the answer is the max of all shortest distances from the source
Number of Closed Islands	same island count, but discard any component that touches the border
Pacific Atlantic Water Flow · ⇩ walkthrough	flood inward from each ocean's edge, then take the intersection of the two reachable sets
Reconstruct Itinerary	lexical tie-break via a per-node min-heap
Rotting Oranges	seed the queue with all rotten cells and run a multi-source BFS, counting layers = minutes
Shortest Bridge	flood one island first, then multi-source BFS outward until you hit the second
Surrounded Regions	first flood the safe cells inward from the borders, then flip everything else
Swim in Rising Water	minimize the maximum cell height along a path (same min-of-max relaxation)
Valid Arrangement of Pairs	pick a start with out−in = 1; Hierholzer
Walls and Gates	sources are all the gates; fill each room with its distance to the closest gate

Segment Tree & Fenwick

Problem	Approach hint
Range Sum Query — Mutable · ⇩ walkthrough	the canonical use — update one index, query any prefix/range

Full Walkthroughs — numbered steps + code

What & why: the ~50 highest-value variations where a step-by-step recipe pays off. Each has an explicit approach, numbered steps, and (where useful) a compact Java sketch.

3Sum Closest

↗ LeetCode · Pattern: Two Pointers

1. Sort. For each i, run two-pointer on [i+1..n-1].
2. At every step compute sum = a[i]+a[lo]+a[hi]; if abs(sum-target) < best, update best.
3. Move lo++ if sum < target, else hi-- — like standard 3Sum but tracking the closest, not exactly target.
4. Return best. O(n²) time.

4Sum

↗ LeetCode · Pattern: Two Pointers

1. Sort. Two outer loops i, j (with i<j), then two-pointer inner search for the remaining pair.
2. Skip duplicates at every level: i>0 && a[i]==a[i-1], j>i+1 && a[j]==a[j-1], and after each hit skip lo/hi duplicates.
3. Use long for the sum to avoid overflow at extreme values.
4. O(n³) time.

Best Time to Buy and Sell Stock

↗ LeetCode · Pattern: 1-pass DP

1. Track minSoFar = min(minSoFar, price[i]).
2. Track best = max(best, price[i] - minSoFar).
3. O(n) time, O(1) space.

Stock with Cooldown

↗ LeetCode · Pattern: State-Machine DP

1. Three states: hold, sold, rest. Transitions:
2. hold' = max(hold, rest - price) (buy today).
3. sold' = hold + price (sell today).
4. rest' = max(rest, sold) (do nothing).
5. Answer = max(sold, rest). O(n) time, O(1) space.

Binary Tree Right Side View

↗ LeetCode · Pattern: BFS (last of each level)

1. BFS with a level size. Push root, then for each level dequeue size nodes.
2. The last one you dequeue in the level is visible — record its value.
3. Push children in normal order.
4. O(n) time.

Candy

↗ LeetCode · Pattern: Greedy (two-pass)

1. Give every child 1 candy.
2. Left-to-right: if r[i] > r[i-1], set c[i] = c[i-1] + 1.
3. Right-to-left: if r[i] > r[i+1], set c[i] = max(c[i], c[i+1] + 1).
4. Sum c. Two passes because each direction enforces only one side of the constraint. O(n).

Capacity To Ship Packages Within D Days

↗ LeetCode · Pattern: Binary Search on Answer

1. Range: lo = max(weights), hi = sum(weights).
2. feasible(cap): sweep, add to current day's load; if it would exceed cap, start a new day; return days <= D.
3. Binary-search the smallest feasible cap. O(n log sum).

Coin Change

↗ LeetCode · Pattern: Unbounded knapsack DP

1. dp[i] = min coins summing to i; init dp[0]=0, others amount+1 (sentinel).
2. For each i from 1 to amount, for each coin c ≤ i: dp[i] = min(dp[i], dp[i-c]+1).
3. Return dp[amount] > amount ? -1 : dp[amount].
4. O(amount · coins).

Combination Sum II

↗ LeetCode · Pattern: Backtracking (each element once + dedup)

1. Sort. Standard combination template with start.
2. At each i: skip if i > start && a[i] == a[i-1] (dedup at level).
3. Recurse with i+1 (no reuse). Break when a[i] > remaining (pruning).
4. Exponential in worst case.

Contiguous Array (equal 0s and 1s)

↗ LeetCode · Pattern: Prefix Sum + Hash

1. Map every 0 to -1 mentally; find the longest subarray with sum 0.
2. Track running sum; store the first index each sum value appeared at.
3. When you revisit a sum, the subarray between is balanced — update best.
4. Seed {0: -1} so runs starting at index 0 are handled. O(n).

Copy List with Random Pointer

↗ LeetCode · Pattern: Hashing on nodes

1. First pass: Map<Node,Node> from original to a fresh clone with same val.
2. Second pass: for each original u, set map[u].next = map[u.next] and map[u].random = map[u.random].
3. Return map[head]. O(n) time and space (or O(1) with interleaved-copy trick).

Counting Bits

↗ LeetCode · Pattern: DP on bits

1. bits[i] = bits[i >> 1] + (i & 1) reuses the answer for i/2.
2. Fill 0..n in one pass.
3. O(n) time.

Critical Connections in a Network

↗ LeetCode · Pattern: Tarjan low-link

1. DFS assigning disc[u] (discovery time) and low[u] (earliest reachable via one back-edge).
2. For a tree edge u → v, recurse then set low[u] = min(low[u], low[v]).
3. If low[v] > disc[u], edge (u,v) is a bridge.
4. Skip the direct parent edge to avoid a false back-edge. O(V+E).

Edit Distance

↗ LeetCode · Pattern: Subsequence DP

1. dp[i][j] = edits from s1[0..i-1] to s2[0..j-1].
2. Match: dp[i-1][j-1]. Else: 1 + min(insert dp[i][j-1], delete dp[i-1][j], replace dp[i-1][j-1]).
3. Bases: empty prefix = length of the other.
4. O(m·n).

Find All Anagrams in a String

↗ LeetCode · Pattern: Sliding Window (fixed size)

1. Build the frequency vector need[26] from p.
2. Slide a window of size |p| over s. Maintain a have[26].
3. Record left in the result whenever have equals need; increment/decrement bounds each step.
4. O(|s|) time.

Find All Numbers Disappeared in an Array

↗ LeetCode · Pattern: Cyclic Sort / index-marking

1. In-place: for each v = |a[i]|, mark a[v-1] = -|a[v-1]| to record that v was seen.
2. After the pass, positive entries mark indices whose value never appeared — add i+1 to the result.
3. O(n) time, O(1) extra.

Find Peak Element

↗ LeetCode · Pattern: Binary Search on the shape

1. nums[-1] = nums[n] = -∞ conceptually.
2. At mid: if a[mid] > a[mid+1], a peak is on the left half (including mid); else on the right.
3. Halve until lo == hi. O(log n).

Find the Duplicate Number

↗ LeetCode · Pattern: Fast/Slow Pointers (Floyd)

1. Treat nums as a functional graph: next(i) = nums[i]. A duplicate value guarantees a cycle.
2. Phase 1: advance slow = nums[slow], fast = nums[nums[fast]] until they meet.
3. Phase 2: reset slow = 0; move both one step at a time until they meet again — that's the cycle start = duplicate.
4. O(n) time, O(1) space.

Fruits into Baskets

↗ LeetCode · Pattern: Sliding Window

1. Reduces to longest subarray with ≤ 2 distinct values.
2. Grow right; when the map holds > 2 distinct fruits, shrink left until back to 2.
3. Track best = max(best, right - left + 1).
4. O(n) time, O(1) space (alphabet ≤ 3).

Generate Parentheses

↗ LeetCode · Pattern: Backtracking (constrained)

1. Track open, close counters starting at 0.
2. Add ( if open < n. Add ) if close < open.
3. When open + close == 2n, record the string.
4. Catalan-number many outputs.

Insert Interval

↗ LeetCode · Pattern: Intervals

1. Emit all intervals ending before newStart (no overlap, left side).
2. Merge every interval overlapping new — grow newStart = min, newEnd = max.
3. Emit the merged new, then emit the rest.
4. O(n) with one pass.

K Closest Points to Origin

↗ LeetCode · Pattern: Top-K Heap or Quickselect

1. Max-heap of size k on squared distance. For each point, offer; if size > k, poll (evict the farthest).
2. Heap ends with the k closest. Or use Quickselect for O(n) average.
3. O(n log k) time.

Kth Smallest Element in a BST

↗ LeetCode · Pattern: In-order traversal

1. In-order visit gives sorted order for a BST.
2. Iterative in-order (stack): push lefts, pop-visit-descend-right; decrement k on each visit.
3. Return the value when k hits 0.
4. O(H + k) time.

Kth Smallest Element in a Sorted Matrix

↗ LeetCode · Pattern: Binary Search on Value

1. Range lo=mat[0][0], hi=mat[n-1][n-1].
2. count(v) — count entries ≤ v by walking from bottom-left in O(n) (down if ≤, else left).
3. Binary-search smallest v with count(v) ≥ k. O(n log range).

Longest Increasing Subsequence

↗ LeetCode · Pattern: Patience DP

1. Maintain a tails list where tails[k] = smallest tail of an LIS of length k+1.
2. For each x, binary-search the first tails[i] >= x and set tails[i] = x; if none, append.
3. Answer = tails.size().
4. O(n log n).

Longest Substring with At Most K Distinct

↗ LeetCode · Pattern: Sliding Window

1. Grow right, tracking a frequency map.
2. While map.size() > k, shrink left: decrement its count; remove key when it hits 0.
3. Update best = max(best, right - left + 1).
4. O(n) time, O(k) space.

Aggressive Cows / Magnetic Force

↗ LeetCode · Pattern: Binary Search on Answer

1. Sort positions. Range lo=1, hi=max-min.
2. feasible(d): greedily place balls at positions ≥ last + d; feasible iff you place all m.
3. Binary-search the largest feasible d. O(n log range).

Maximum Product Subarray

↗ LeetCode · Pattern: 1D DP (Kadane variant)

1. Track both a running maxSoFar and minSoFar — a negative flips them.
2. At each x: newMax = max(x, x*maxSoFar, x*minSoFar); newMin = min(x, x*maxSoFar, x*minSoFar).
3. Update best = max(best, newMax) each step.
4. O(n) time, O(1) space.

Meeting Rooms

↗ LeetCode · Pattern: Intervals

1. Sort by start time.
2. Return false as soon as a[i].start < a[i-1].end.
3. Otherwise true. O(n log n).

Missing Number

↗ LeetCode · Pattern: XOR / Gauss sum

1. XOR trick: xor(0..n) ^ xor(nums) — all pairs cancel, missing survives.
2. Or sum trick: n(n+1)/2 - sum(nums).
3. O(n) time, O(1) space.

Move Zeroes

↗ LeetCode · Pattern: Two Pointers (write index)

1. Keep a write index starting at 0.
2. Scan read left-to-right: whenever a[read] != 0, set a[write++] = a[read].
3. After the scan, fill a[write..n-1] with 0.
4. In-place, order-preserving, O(n).

My Calendar I

↗ LeetCode · Pattern: Intervals / TreeMap

1. Store bookings in a TreeMap keyed by start.
2. For a new [s,e): check floorKey(s) and ceilingKey(s) — conflict iff their intervals overlap [s,e).
3. Insert on success. O(log n) per booking.

Network Delay Time

↗ LeetCode · Pattern: Dijkstra

1. Standard Dijkstra from k.
2. If any distance stays ∞, return -1.
3. Otherwise return max(dist).
4. O(E log V).

Next Greater Element I

↗ LeetCode · Pattern: Monotonic Stack

1. Compute NGE for each value in nums2 using a decreasing stack; store value → next-greater in a map.
2. For each query in nums1, look it up in the map (default -1).
3. O(n + m) time.

Number of Provinces

↗ LeetCode · Pattern: Union-Find

1. For each (i, j) with M[i][j] == 1, union(i, j).
2. Count distinct find(i) values.
3. O(n² α(n)).

Online Stock Span

↗ LeetCode · Pattern: Monotonic Stack

1. Keep a stack of (price, span) pairs, decreasing by price.
2. On next(price): pop and accumulate span while the top's price ≤ current. Push (price, span).
3. Each pushed pair is popped at most once — amortized O(1) per query.

Pacific Atlantic Water Flow

↗ LeetCode · Pattern: Multi-source BFS/DFS

1. Two visited grids: pac, atl.
2. BFS/DFS from every edge cell of each ocean, but only step to neighbours not lower (reverse-flow).
3. Result cells are those visited by both pac and atl.
4. O(m·n) time.

Palindrome Partitioning

↗ LeetCode · Pattern: Backtracking + palindrome check

1. DFS the split points. At each recursion, try every next-cut position end.
2. If s[start..end] is a palindrome, add and recurse from end+1.
3. Precompute an isPal[i][j] DP for O(1) palindrome test.
4. Exponential in worst case.

Permutation in String

↗ LeetCode · Pattern: Sliding Window (fixed size)

1. Same as Find All Anagrams, but return true on the first match instead of collecting positions.
2. Fixed window size = |s1|; compare counts each shift.
3. O(|s2|) time.

Permutations II

↗ LeetCode · Pattern: Backtracking (dedup by used[] rule)

1. Sort. Use used[i] to track picked indices.
2. Skip when i > 0 && a[i] == a[i-1] && !used[i-1] — enforces first-copy-first ordering.
3. Recurse when path.size() == n.
4. O(n·n!) time.

Random Pick with Weight

↗ LeetCode · Pattern: Prefix Sum + Binary Search

1. Build a prefix sum of weights.
2. For each pick, generate r = rnd.nextInt(total) + 1.
3. Binary-search the smallest index whose prefix sum ≥ r.
4. O(n) build, O(log n) per pick.

Range Addition

↗ LeetCode · Pattern: Difference Array

1. Maintain a delta array. For each update [l, r, val], do diff[l] += val; diff[r+1] -= val.
2. After all updates, prefix-sum the delta array to recover the final values.
3. O(U + n) total, vs O(U·n) naive.

Range Sum Query — Mutable

↗ LeetCode · Pattern: Fenwick Tree

1. Build 1-indexed BIT: for each i, tree[i] = sum of the last i&-i values.
2. update(i, delta): walk i += i & -i while i ≤ n, adding delta.
3. sum(i): walk i -= i & -i while i > 0, accumulating.
4. Query [l,r] = sum(r) - sum(l-1). O(log n) each op.

Reverse Nodes in k-Group

↗ LeetCode · Pattern: Linked List

1. Advance a pointer k steps; if fewer than k remain, return without reversing.
2. Reverse the k-node block in place (standard three-pointer reverse).
3. Wire the tail of the reversed block to the recursive result of the rest.
4. O(n) time, O(1) space (iterative).

Search a 2D Matrix

↗ LeetCode · Pattern: Binary Search

1. Row-major sorted array reshaped as a matrix — treat as one 1D sorted array of size m*n.
2. Binary-search lo=0, hi=m*n-1; map mid to (mid/n, mid%n).
3. Compare mat[r][c] to target; standard halving.
4. O(log(mn)) time.

Search a 2D Matrix II

↗ LeetCode · Pattern: Two Pointers on a matrix

1. Start at the top-right corner (0, n-1).
2. If mat[r][c] == target, done. If mat[r][c] > target, c-- (eliminates a column). Else r++ (eliminates a row).
3. Each step drops a row or column, so O(m+n) total.
4. Bottom-left works symmetrically.

Shuffle an Array (Fisher–Yates)

↗ LeetCode · Pattern: Randomized

1. Copy the array to a mutable buffer.
2. For i from n-1 down to 1: swap buf[i] with buf[rnd.nextInt(i+1)].
3. Every permutation has equal probability by induction.
4. O(n) per shuffle.

Spiral Matrix II

↗ LeetCode · Pattern: Matrix mechanics

1. Same layer-by-layer walk as Spiral Matrix, but write 1..n² into the cells you visit.
2. Maintain top, bot, left, right bounds; after each side, shrink the relevant bound.
3. Guard bottom-row and left-column with top <= bot / left <= right for odd n.
4. O(n²) time, O(1) extra.

Subarray Sums Divisible by K

↗ LeetCode · Pattern: Prefix Sum + Hash

1. Prefix sum modulo k — two prefix sums with the same residue bracket a subarray whose sum is a multiple of k.
2. Count occurrences of each residue ((prefix % k) + k) % k (handle negatives).
3. For each new residue, add its running count to the answer, then increment.
4. Seed the count map with {0: 1} for subarrays that start at index 0. O(n).

Subsets II

↗ LeetCode · Pattern: Backtracking (dedup by sort + skip)

1. Sort. Standard subsets template with start index.
2. Inside the for-loop: if i > start && a[i] == a[i-1] skip — prevents same-level twins.
3. Record a copy of the path at every node.
4. O(2ⁿ) subsets.

Two Sum II — Input Array Is Sorted

↗ LeetCode · Pattern: Two Pointers

1. Two indices lo=0, hi=n-1.
2. Compute sum = a[lo] + a[hi]; if it equals target return {lo+1, hi+1} (1-indexed).
3. If sum is too small, lo++; too big, hi--. Sortedness guarantees the discarded end can never help.
4. Terminates when pointers cross — O(n) time, O(1) space.

int lo=0, hi=a.length-1;
while (lo<hi) {
    int s=a[lo]+a[hi];
    if (s==target) return new int[]{lo+1, hi+1};
    if (s<target) lo++; else hi--;
}
return new int[]{-1,-1};

Unique Paths

↗ LeetCode · Pattern: Grid DP

1. dp[i][j] = dp[i-1][j] + dp[i][j-1]; first row/col all 1s.
2. Collapse to a 1D row updated left-to-right — O(n) space.
3. Answer at dp[m-1][n-1].
4. O(m·n).

Valid Anagram

↗ LeetCode · Pattern: Hashing

1. Return false if lengths differ.
2. Bump count[c]++ for each char in s, decrement for each char in t.
3. Return true iff every count is 0 (or every entry in the map is 0).
4. O(n) time, O(1) space for fixed alphabet.

Valid Palindrome II

↗ LeetCode · Pattern: Two Pointers

1. Standard two-pointer palindrome check.
2. On the first mismatch, allow one skip: try s[lo+1..hi] or s[lo..hi-1] — return true if either is a palindrome.
3. Only one deletion is allowed, so this branching is sufficient.
4. O(n) time.

Word Break

↗ LeetCode · Pattern: 1D DP

1. dp[i] = can we split s[0..i-1] into dictionary words.
2. dp[0] = true; for each i, try every j < i — dp[i] = dp[j] && s[j..i-1] ∈ dict.
3. Use a HashSet for O(1) lookups.
4. O(n²·L) time.

Word Ladder

↗ LeetCode · Pattern: BFS

1. Put every word into a set (dedup + O(1) lookup).
2. BFS from beginWord; at each pop, generate every 1-letter variant, if in set, enqueue and remove from set.
3. Distance += 1 per level; return when you dequeue endWord.
4. O(N·L·Σ) time.