Divide and Conquer
Intermediate · 22 min read · Problem-Solving Patterns, Searching & Sorting
Split, solve, combine: counting during merge sort, the crossing case, splitting at what can't belong, and the master theorem.
Divide and conquer solves a problem by splitting it into smaller independent pieces, solving each piece recursively, and combining the answers. You've already used it without the name: merge sort, quickselect, building a tree from its traversals, and every "solve the left subtree, solve the right subtree" recursion.
The three steps
All the thinking goes into step 3. If combining is cheap, the algorithm is fast. If you can't say how to combine, divide and conquer is the wrong tool.
Complexity: the master theorem, practically
A divide-and-conquer algorithm that splits into a pieces of size n / b and spends O(nᵈ) dividing and combining has
Pattern 1: count while you merge
Many "count the pairs" problems look like they need O(n²) comparisons. Merge sort fixes that because, at the moment two sorted halves are merged, every element of the left half has a known relationship to every element of the right half.
Pattern 2: the crossing case
Some problems ask for the best contiguous piece. Split at the middle: the best piece is entirely on the left, entirely on the right, or it crosses the middle. The first two are recursive calls; the crossing case is the best suffix of the left half plus the best prefix of the right half, computed in O(n).
Pattern 3: split at what can't belong
Sometimes the input contains elements that no valid answer can include. They cut the problem into independent pieces, and you recurse on each.
Pattern 4: choose the last operation
"Return every result of every way to parenthesise 2*3-4*5". Every grouping applies some operator last. Choose it, and the expression splits into a left part and a right part whose results can be computed independently:
Pattern 5: sort what you can't index
Merge sort needs only sequential access, which makes it the natural O(n log n) sort for linked lists:
Practice ladder
Interview questions
- What is the time complexity of T(n) = 2T(n/2) + O(n), and why?
- How does merge sort count inversions in O(n log n)?
- When does divide and conquer become dynamic programming?
Practice
Write your answer before opening the suggested one. Anything you mark "Partly" or "Missed it" comes back in your review deck.
Further reading
Key takeaways
- Divide, conquer, combine. The combine step decides whether the approach works and how fast it is.
- Complexity: count the levels and the work per level; the master theorem formalises T(n) = aT(n/b) + O(nᵈ).
- Merge sort turns O(n²) pair counting into O(n log n): count across halves while (or just before) merging.
- For contiguous answers, the crossing case is the best suffix of the left plus the best prefix of the right.
- Elements that can't be in any answer split the input into independent pieces.
- "All ways to group" means choose the last operation; when pieces repeat, memoise, and you have interval DP.
- Merge sort is the natural O(n log n) sort for linked lists; bottom-up merge sort uses O(1) extra space.