Divide & Conquer

From “recursive code” to professional algorithm design.

The real definition

Divide-and-conquer is not “use recursion.”

It is:

1. define a precise subproblem boundary;
2. solve smaller independent boundaries;
3. combine child answers without reopening them.

Speaker note: Keep repeating “boundary + contract.” That is the module’s central idea.

The five questions

Before coding, answer:

1. What does one call own?
2. What does one call return?
3. What is already solved?
4. How do we split without losing data?
5. How do we combine child answers?

If one answer is vague, the code will be fragile.

Boundary examples

Most divide-and-conquer bugs are boundary bugs.

Pattern: sorted array to balanced BST

Contract:

build(lo, hi) returns a balanced BST containing nums[lo..hi]

Move:

choose middle as root
left range  = lo..mid-1
right range = mid+1..hi

Why middle? Because it keeps subtree sizes close.

Sorted array trace

[-10, -3, 0, 5, 9]

root = 0
left = [-10, -3]
right = [5, 9]

One valid tree:

        0
      /   \
   -10     5
      \     \
      -3     9

Tests should check properties, not one exact shape.

Pattern: merge sort on linked list

Contract:

SortList(head) returns a sorted list containing exactly the same nodes

Critical move:

prev.Next = nil

Finding the midpoint is not enough. You must physically cut the list.

Linked-list split

before:
4 -> 2 -> 1 -> 3

split:
4 -> 2    1 -> 3

Then recursively sort both halves and merge.

Failure mode: if the first half still points into the second half, recursion may never shrink.

Pattern: merge k sorted lists

Bad sequential merge:

((L0 + L1) + L2) + L3 ...

Balanced pairwise merge:

round 1: (L0+L1), (L2+L3), (L4+L5)
round 2: previous pairs merge again

Each round touches all nodes once.

Runtime: O(n log k).

Merge k trace

L0 = 1 -> 4 -> 5
L1 = 1 -> 3 -> 4
L2 = 2 -> 6

Round 1:

merge L0,L1 => 1 -> 1 -> 3 -> 4 -> 4 -> 5
carry L2    => 2 -> 6

Round 2:

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Pattern: quad tree

Contract:

build(r0, c0, size) returns the node for exactly that square

If the square is uniform, return a leaf.

Otherwise split into:

top-left, top-right, bottom-left, bottom-right

Quad tree boundaries

For half = size / 2:

TL: (r0,      c0,      half)
TR: (r0,      c0+half, half)
BL: (r0+half, c0,      half)
BR: (r0+half, c0+half, half)

Coordinate mistakes are common because the tree shape may still look valid.

Cost model

Ask: what is the work per level?

Sorted array to BST:

each element is used once => O(n)

Linked-list merge sort:

O(n) per level * O(log n) levels => O(n log n)

Merge k lists:

O(n) per round * O(log k) rounds => O(n log k)

Professional upgrade: avoid repeated scans

Naive quad tree uniformity scan:

can scan O(n^2) cells per level
worst case O(n^2 log n)

Prefix sum uniformity check:

ones in region == 0    => all zero
ones in region == area => all one
otherwise mixed

Preprocess once, query regions in O(1).

Correctness template

Contract: what this call returns.
Base case: smallest boundary is solved directly.
Induction: assume children are correct.
Split: children cover parent exactly.
Combine: parent result follows from child results.
Termination: boundaries strictly shrink.

This template works for every problem in this module.

Final checklist

Before submission:

• Did every recursive call get a smaller input?
• Did the split cover all data exactly once?
• Did you handle empty and one-item inputs?
• Did pointer code avoid cycles?
• Did tests verify properties, not just examples?