Divide & Conquer
Split the input, solve the halves recursively, and do the real work while combining them.
SortingUsually O(n log n)New14 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
merge sort
count inversions
quickselect
median of two sorted arrays
The template
Get this into muscle memory, then adapt the condition per problem.
function solve(lo: number, hi: number) {
if (lo >= hi) return base;
const mid = (lo + hi) >> 1;
const L = solve(lo, mid), R = solve(mid + 1, hi);
return merge(L, R);
} Watch Merge SortIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Can the problem be answered for two halves independently?
- 2The interesting work usually happens across the boundary.
- 3Count cross-pairs during the merge step.
Drill it
Every problem in the bank that uses this pattern.
0 / 14 solved