Divide and Conquer Pattern
The Idea
Divide and conquer solves a problem by:
1. DIVIDE — split the input into smaller pieces of the same kind
2. CONQUER — solve each piece recursively (tiny pieces are solved directly)
3. COMBINE — merge the pieces' answers into the answer for the whole
problem(n)
/ \
problem(n/2) problem(n/2) ← independent: no shared work
... ...
\ /
combine(left, right) ← where the real cleverness lives
You have already seen it in Merge Sort, Quick Sort, and Binary Search. This page focuses on applying the pattern to new problems — and the key question is always: what does the combine step need to know?
Example 1: Fast Power
Computing xⁿ by multiplying n times is O(n). Splitting the exponent in half:
x^n = (x^(n/2))² if n is even x^n = (x^(n/2))² · x if n is odd (n/2 rounded down) 3^13: 3^13 = (3^6)² · 3 3^6 = (3^3)² 3^3 = (3^1)² · 3 3^1 = (3^0)² · 3 = 3 4 levels, ~2 multiplications each → O(log n) instead of 12 multiplications
The divide step makes one sub-problem (not two) — that's why it's logarithmic. With a modulus, this computes values like 2¹⁰⁰ mod 1,000,000,007 without ever forming the huge number.
Example 2: Counting Out-of-Order Pairs
A ranking is "mostly sorted" if few pairs are out of order. Count the pairs i < j with a[i] > a[j] (often called inversions).
ranks = [2, 4, 1, 3, 5]
out-of-order pairs: (2,1) (4,1) (4,3) → 3
Brute force: check every pair → O(n²)
DIVIDE & CONQUER:
total = pairs inside left half
+ pairs inside right half
+ pairs with one value in each half ← the combine step
Counting cross pairs is easy if both halves are SORTED —
so piggy-back on merge sort:
left = [2, 4] right = [1, 3, 5] (each sorted)
merge:
1 (right) < 2 → 1 is smaller than ALL remaining left values {2, 4} → +2
2 (left)
3 (right) < 4 → +1 (only {4} remains in left)
4 (left)
5 (right) — left is empty → +0
cross = 3
Merging already costs O(n), and counting adds O(1) per step, so the whole thing stays O(n log n).
Example 3: Best Contiguous Total
Given daily changes (positive and negative), find the largest total over any contiguous run of days.
changes = [3, -5, 4, -1, 2, -6, 5, -2]
The best run is entirely in the LEFT half, entirely in the RIGHT half,
or it CROSSES the middle.
crossing run = (best sum ending at mid, walking left)
+ (best sum starting at mid+1, walking right)
left half [3, -5, 4, -1]: best ending at index 3: -1+4 = 3
right half [2, -6, 5, -2]: best starting at index 4: 2
crossing best = 3 + 2 = 5 ([4, -1, 2])
Overall best = max(left best, right best, crossing) = 5
T(n) = 2T(n/2) + O(n) = O(n log n). (A one-pass DP solves this in O(n); the D&C version is still worth knowing because the "crossing" idea generalises — e.g. to segment trees that answer this query on any range.)
Code: Fast Power, Out-of-Order Pairs, Best Total
import java.util.Arrays;
public class DivideAndConquer {
static final long MOD = 1_000_000_007L;
// 1. Fast power: x^n from x^(n/2) — O(log n) multiplications
static long power(long x, long n, long mod) {
if (n == 0) return 1 % mod;
long half = power(x, n / 2, mod); // divide: ONE sub-problem of half size
long result = half * half % mod; // combine
return (n % 2 == 1) ? result * (x % mod) % mod : result;
}
// 2. Count out-of-order pairs while merge sorting a[lo..hi)
static long sortAndCount(int[] a, int[] tmp, int lo, int hi) {
if (hi - lo <= 1) return 0;
int mid = (lo + hi) / 2;
long count = sortAndCount(a, tmp, lo, mid) + sortAndCount(a, tmp, mid, hi); // divide
int i = lo, j = mid, k = lo; // combine
while (i < mid && j < hi) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else { tmp[k++] = a[j++]; count += mid - i; } // smaller than every remaining left value
}
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
System.arraycopy(tmp, lo, a, lo, hi - lo);
return count;
}
// 3. Best contiguous total: left, right, or crossing the middle
static long bestTotal(int[] a, int lo, int hi) {
if (lo == hi) return a[lo];
int mid = (lo + hi) / 2;
long bestLeft = bestTotal(a, lo, mid), bestRight = bestTotal(a, mid + 1, hi);
long run = 0, leftReach = Long.MIN_VALUE; // best sum ending exactly at mid
for (int i = mid; i >= lo; i--) { run += a[i]; leftReach = Math.max(leftReach, run); }
run = 0;
long rightReach = Long.MIN_VALUE; // best sum starting exactly at mid+1
for (int i = mid + 1; i <= hi; i++) { run += a[i]; rightReach = Math.max(rightReach, run); }
return Math.max(Math.max(bestLeft, bestRight), leftReach + rightReach);
}
public static void main(String[] args) {
System.out.println("3^13 = " + power(3, 13, MOD));
System.out.println("2^100 mod 1e9+7 = " + power(2, 100, MOD));
for (int[] ranks : new int[][]{{2, 4, 1, 3, 5}, {5, 4, 3, 2, 1}, {1, 2, 3}}) {
String label = Arrays.toString(ranks);
long inv = sortAndCount(ranks, new int[ranks.length], 0, ranks.length);
System.out.println("out-of-order pairs in " + label + ": " + inv);
}
int[] changes = {3, -5, 4, -1, 2, -6, 5, -2};
System.out.println("best contiguous total in " + Arrays.toString(changes) + ": "
+ bestTotal(changes, 0, changes.length - 1));
}
}Output:
3^13 = 1594323
2^100 mod 1e9+7 = 976371285
out-of-order pairs in [2, 4, 1, 3, 5]: 3
out-of-order pairs in [5, 4, 3, 2, 1]: 10
out-of-order pairs in [1, 2, 3]: 0
best contiguous total in [3, -5, 4, -1, 2, -6, 5, -2]: 5
The JavaScript version uses BigInt (the n suffix) for fast power because products of two numbers near 10⁹ exceed the 2⁵³ limit of exact integers in a regular JS number.
Analysing Divide & Conquer: The Master Theorem
Most D&C running times have the form T(n) = a · T(n / b) + f(n): a sub-problems, each of size n / b, plus f(n) work to divide and combine.
Compare f(n) with n^(log_b a) — the total size of the leaf level. CASE 1 f(n) grows slower → leaves dominate T(n) = Θ(n^(log_b a)) CASE 2 f(n) grows the same → every level equal T(n) = Θ(n^(log_b a) · log n) CASE 3 f(n) grows faster → root dominates T(n) = Θ(f(n)) EXAMPLES Binary search T(n) = T(n/2) + O(1) a=1,b=2 → n^0 = 1 vs 1 → Θ(log n) Fast power T(n) = T(n/2) + O(1) same → Θ(log n) Merge sort T(n) = 2T(n/2) + O(n) n^1 vs n → Θ(n log n) Out-of-order pairs T(n) = 2T(n/2) + O(n) same → Θ(n log n) Tree traversal T(n) = 2T(n/2) + O(1) n^1 vs 1 (case 1) → Θ(n) Naive matrix mult. T(n) = 8T(n/2) + O(n²) n^3 vs n² (case 1) → Θ(n³) Strassen T(n) = 7T(n/2) + O(n²) n^2.81 vs n² → Θ(n^2.81)
The Strassen line shows the classic D&C win: reducing the number of sub-problems (8 → 7) lowers the exponent.
How to Spot It
✓ The answer for the whole can be built from answers for two halves plus something that "crosses" the split ✓ Brute force looks at all pairs (O(n²)), and sorting halves would make counting cross pairs easy → merge-sort-style counting ✓ Repeated operations that compose (powers, matrix powers, function composition) → halve the exponent ✓ Tree-shaped data — every subtree is a smaller instance ✓ Geometry: closest pair of points, convex hull — split by a line
D&C vs DP vs Greedy
SUB-PROBLEMS TYPICAL COST EXAMPLE Divide & Conquer independent, split O(n log n) / O(log n) merge sort, fast power Dynamic Prog. overlapping, reused O(states × choices) knapsack, edit distance Greedy one choice per step O(n log n) interval scheduling If a D&C recursion keeps solving the SAME sub-problem → add a cache → it's DP.
Common Mistakes
Calling the sub-problem twice when once is enough. Writing power(x, n/2) * power(x, n/2) makes two recursive calls and turns O(log n) back into O(n). Compute it once and square it.
Forgetting the crossing case. Splitting "best run" into left and right halves misses runs that straddle the middle — the combine step must handle them.
Overflow in modular multiplication. half * half overflows 32-bit ints long before the modulus does. Use 64-bit types (and BigInt in JS when values approach 10⁹).
Uneven splits. Quick sort with a bad pivot splits n into 1 and n − 1, giving O(n²). D&C is fast only when pieces shrink by a constant factor.
Interview Questions
Q: Why does counting out-of-order pairs need the halves sorted?
Once both halves are sorted, a right-half value that comes before left[i] in the merge is smaller than left[i] and every value after it. That lets you count all of its cross pairs in O(1) — the number of left values remaining — instead of comparing it with each one.
Q: Write the recurrence for fast power and solve it.
T(n) = T(n/2) + O(1): one sub-problem of half the size and constant combine work. Unrolling gives O(1) per level over log₂ n levels: O(log n).
Q: When is divide and conquer the wrong tool?
When the sub-problems overlap (use DP), when splitting doesn't make the combine step easier than solving directly, or when a single linear scan already solves the problem — like the best contiguous total, where a one-pass DP is O(n) versus D&C's O(n log n).
Summary
- ›Divide into independent pieces, conquer recursively, combine — the combine step holds the insight.
- ›Fast power: one half-size sub-problem → O(log n).
- ›Out-of-order pairs: count cross pairs during merge sort → O(n log n).
- ›Best contiguous total: left, right, or crossing → O(n log n).
- ›Analyse with T(n) = a·T(n/b) + f(n) and the master theorem.
Next, Heap Pattern keeps the best k items — or the current minimum — available in O(log n), the engine behind "top k", "k-way merge", and scheduling problems.
What are the three steps of divide and conquer?