Divide & Conquer

Divide and conquer is the discipline of solving a problem by giving each recursive call a smaller, honest contract.

The beginner version is: “split the input, recurse, combine.”

The professional version is sharper:

A divide-and-conquer algorithm is correct when every subproblem owns a precise boundary, solves that boundary completely, and returns exactly the information the parent needs to combine results without looking inside the child.

This module focuses less on memorizing four solutions and more on learning how to design the recursive contract, choose safe boundaries, prove correctness, and analyze the recursion tree.

What you should be able to do after this module

By the end, you should be able to:

1. Decide whether a problem is actually divide-and-conquer or merely recursive.
2. Define the subproblem boundary before writing code.
3. Pick base cases that terminate and preserve meaning.
4. Split arrays, linked lists, list collections, and grids without off-by-one bugs.
5. Write the combine step without corrupting pointers or losing data.
6. Explain the runtime from a recursion tree instead of guessing.
7. Recognize when divide-and-conquer is worse than another tool, such as a heap, dynamic programming, or a prefix-sum preprocessing step.

The core mental model

Every recursive call should be treated like a black-box worker.

You give the worker a smaller piece of the original problem. The worker promises to solve exactly that piece and return a result in a known shape. The parent is not allowed to fix the child’s internal mistakes. The parent is only allowed to combine child results.

That means every divide-and-conquer solution has five parts:

If you cannot fill this table for a problem, coding first will usually create a messy recursive function that works only by accident.

Divide-and-conquer versus plain recursion

Not every recursive solution is divide-and-conquer.

A recursive DFS over a tree is recursive, but not necessarily divide-and-conquer. It becomes divide-and-conquer when each child subtree is an independent subproblem and the parent combines child answers.

Backtracking is also recursive, but it usually explores choices while sharing global constraints. A Sudoku solver does not split the board into independent boards. Choices interact with each other. That is not classic divide-and-conquer.

Dynamic programming may look similar because it solves smaller subproblems, but DP is used when subproblems overlap. Divide-and-conquer is strongest when subproblems are mostly independent.

Use this test:

If solving the left child can change what the right child is allowed to do, the problem is probably not pure divide-and-conquer.

The boundary is the algorithm

Most bugs in this module are not “recursion bugs.” They are boundary bugs.

A boundary is the exact portion of the input a call owns. There are several common boundary styles.

Pick one boundary convention and stay loyal to it. Mixing conventions is the source of many off-by-one errors.

A reusable design checklist

Before writing the first line of code, answer these in order.

1. What does one call mean?

Example for sorted array to BST:

build(lo, hi) returns the root of a height-balanced BST containing exactly nums[lo..hi].

Example for quad tree:

build(r0, c0, size) returns the quad-tree node representing exactly the square whose top-left cell is (r0,c0) and whose side length is size.

This one sentence is the contract. Everything else follows from it.

2. What is the smallest honest problem?

A base case is not just a stopping condition. It must return the correct answer for the smallest piece.

For an empty array range, the correct tree is nil.

For a one-node linked list, the correct sorted list is the same node.

For a uniform grid region, the correct quad-tree representation is one leaf, even if the region has many cells.

3. How do we split without losing or duplicating data?

For lo..hi, choosing mid gives:

left:  lo..mid-1
root:  mid
right: mid+1..hi

Every index appears exactly once.

For linked-list merge sort, the split is physical:

before: 4 -> 2 -> 1 -> 3
cut:          ^
after:  4 -> 2    and    1 -> 3

If you find the midpoint but do not cut the list, both recursive calls may still see overlapping nodes. That can cause infinite recursion or cycles.

4. What does combine assume?

Combine is allowed to assume child contracts are true.

For merge sort, after recursion:

left  is sorted
right is sorted

So combine does not sort from scratch. It only performs a linear merge.

For BST construction, after recursion:

left subtree contains values before mid
right subtree contains values after mid

So combine only attaches children to a root.

5. What is the recursion tree cost?

Do not memorize Big-O blindly. Draw levels.

For linked-list merge sort:

level 0: merge work n
level 1: merge work n/2 + n/2 = n
level 2: merge work n/4 + n/4 + n/4 + n/4 = n
number of levels: log n
Total: O(n log n)

For sorted array to BST:

each element becomes a node exactly once
Total: O(n)
Height: O(log n)

For pairwise merging k lists with n total nodes:

each round touches every node once
number of rounds: log k
Total: O(n log k)

For naive quad-tree construction:

At each tree level, uniformity scans can add up to O(n^2).
There are O(log n) levels in the worst case.
Naive worst case: O(n^2 log n).

A prefix-sum version can check whether a region is all zero or all one in O(1), after O(n^2) preprocessing. That makes the construction proportional to the number of quad-tree nodes, with O(n^2) preprocessing.

Pattern 1: Build a balanced BST from a sorted array

Problem shape

You have sorted data and must produce a height-balanced binary search tree.

The sorted array already contains the inorder traversal of the target BST. The only real decision is which value becomes the root.

Why the middle element?

A BST requires:

all values in left subtree  < root
all values in right subtree > root

Because the array is sorted, any index can be used as root while preserving the BST property. But balance requires the left and right subtrees to have similar sizes. The middle index is the only local choice that guarantees that.

For:

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

Pick 0 as root:

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

Both sides are smaller sorted arrays. That is the divide-and-conquer opening.

Recursive contract

build(lo, hi) returns the root of a height-balanced BST containing exactly nums[lo..hi].

Base case

if lo > hi: return nil

An empty range has no node.

Split

mid = lo + (hi-lo)/2

Use this form instead of (lo+hi)/2. It avoids overflow in languages where integer overflow is a risk. Go int is usually large enough for this problem, but the habit is good.

Combine

root.Val = nums[mid]
root.Left = build(lo, mid-1)
root.Right = build(mid+1, hi)
return root

Walkthrough

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

build(0,4)
  mid = 2, root = 0

  build(0,1)
    mid = 0, root = -10
    build(0,-1) => nil
    build(1,1)
      mid = 1, root = -3

  build(3,4)
    mid = 3, root = 5
    build(3,2) => nil
    build(4,4)
      mid = 4, root = 9

One valid output:

        0
      /   \
   -10     5
      \     \
      -3     9

Another implementation may pick the upper middle and produce a different but still valid balanced BST. Tests should verify the properties, not one exact shape.

Correctness proof

We prove the contract by induction on the number of elements in nums[lo..hi].

Base case: if the range is empty, returning nil is the correct BST for zero elements.

Inductive step: assume recursive calls correctly build balanced BSTs for smaller ranges. The algorithm picks nums[mid] as root. All elements in lo..mid-1 are less than or equal to values before the root position, and all elements in mid+1..hi are greater than or equal to values after the root position according to the sorted order. The recursive calls return valid BSTs for exactly those ranges. Attaching them to the root preserves inorder order. Because the midpoint splits the range into sizes differing by at most one, the resulting tree is height-balanced.

Complexity

Each element creates one node, so time is O(n).

The recursion depth is the height of the balanced tree, so auxiliary stack space is O(log n).

Failure modes

Using the first element as root creates a linked-list-shaped tree.

Using slices like nums[:mid] and nums[mid+1:] is readable but can obscure boundaries and allocation behavior. Indices are clearer for algorithm training.

Testing only inorder traversal is weak. A skewed tree can still have the correct inorder traversal. Strong tests also check height balance.

Pattern 2: Merge sort on a linked list

Problem shape

You need to sort a singly linked list in O(n log n) time.

Arrays support random access, so array merge sort can split by index. A singly linked list does not. The split must be discovered by walking pointers.

Why merge sort fits linked lists

Quicksort depends heavily on partitioning and random-ish access. Heap sort requires array indexing. Merge sort only needs sequential access and pointer rewiring. That makes it the natural professional choice for linked-list sorting.

Recursive contract

SortList(head) returns the head of a sorted list containing exactly the nodes reachable from head.

The phrase “exactly the nodes” matters. A good linked-list sort should reuse nodes, not allocate a new list of values.

Base case

if head == nil or head.Next == nil: return head

Empty and one-node lists are already sorted.

Split with slow and fast pointers

The slow pointer moves one step. The fast pointer moves two steps. When fast reaches the end, slow is near the middle.

For four nodes:

4 -> 2 -> 1 -> 3
s
f

step 1:
4 -> 2 -> 1 -> 3
     s
          f

step 2:
4 -> 2 -> 1 -> 3
          s
                f is nil

Keep prev, the node before slow, then cut:

prev.Next = nil

Now the two recursive calls are independent:

left:  4 -> 2
right: 1 -> 3

Without this cut, the left half still points into the right half.

Combine with linear merge

After recursion, assume:

left  = sorted list
right = sorted list

The merge step repeatedly takes the smaller head node.

left:  2 -> 4
right: 1 -> 3

pick 1
pick 2
pick 3
pick 4

Using <= instead of < preserves the original relative order of equal values from the left side. That makes the merge stable.

Full walkthrough

input: 4 -> 2 -> 1 -> 3

SortList(4 -> 2 -> 1 -> 3)
  split into:
    4 -> 2
    1 -> 3

  SortList(4 -> 2)
    split into 4 and 2
    merge => 2 -> 4

  SortList(1 -> 3)
    split into 1 and 3
    merge => 1 -> 3

  merge 2 -> 4 and 1 -> 3
    result: 1 -> 2 -> 3 -> 4

Correctness proof

We prove by induction on list length.

Base case: length zero or one is already sorted and contains exactly the original nodes.

Inductive step: the slow/fast split cuts the list into two smaller disjoint lists whose nodes together are exactly the original nodes. By induction, recursive calls return sorted versions of those two lists. The merge routine preserves sorted order by always selecting the smallest available head. It also appends every node from both lists exactly once. Therefore the returned list is sorted and contains exactly the original nodes.

Complexity

Each level merges all nodes once: O(n) work per level.

The split halves the list, so there are O(log n) levels.

Total time: O(n log n).

Auxiliary recursion stack: O(log n).

Pointer extra space: O(1) excluding recursion.

Failure modes

Forgetting prev.Next = nil is the classic serious bug.

Using arrays is simpler but defeats the point of the linked-list pattern.

Returning the dummy node instead of dummy.Next adds a fake value.

Not checking for cycles in tests allows pointer bugs to pass.

Pattern 3: Merge k sorted lists with balanced pairwise merging

Problem shape

You have k sorted linked lists with n total nodes. You need one sorted list.

There are three common strategies:

This module uses pairwise merging because it strengthens the divide-and-conquer idea.

Why sequential merging is bad

Suppose every list has the same size m, so n = k*m.

Sequential merge does this:

merge list 1 + list 2       => 2m work
merge result + list 3       => 3m work
merge result + list 4       => 4m work
...
merge result + list k       => km work

Total work is roughly:

m * (2 + 3 + ... + k) = O(m*k^2) = O(k*n)

Balanced pairwise merging avoids repeatedly dragging a huge accumulator through tiny lists.

Round-based contract

After each round, every list in lists is sorted and contains the nodes of one or more original lists.

At the start, the contract is true because each input list is already sorted.

Each round merges pairs:

round 0:
  L0, L1, L2, L3, L4

round 1:
  merge(L0,L1), merge(L2,L3), L4

round 2:
  merge(previous0, previous1), L4

round 3:
  merge(previous0, L4)

The number of lists shrinks by about half each round.

Walkthrough

Input:

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

Round 1:

merge L0 and L1:
1 -> 1 -> 3 -> 4 -> 4 -> 5

carry L2:
2 -> 6

Round 2:

merge both remaining lists:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

This is not a heap trace. A heap solution would repeatedly pop the minimum head. This module’s reference solution is pairwise divide-and-conquer, so the teaching trace should match that.

Correctness proof

At the start of every round, each list is sorted and represents the merge of some disjoint subset of original lists.

When two such lists are merged with the correct two-list merge routine, the result is sorted and contains exactly the nodes from both subsets. If a list has no partner in an odd-length round, carrying it forward preserves the invariant.

The number of lists decreases until one remains. By the invariant, the final list is sorted and contains all original nodes.

Complexity

Each round touches every node once across all pairwise merges.

There are ceil(log2(k)) rounds.

Total time: O(n log k).

Extra pointer space: O(1) for merging, plus O(k) for the temporary slice of list heads. The nodes themselves are reused.

When a heap is better

A heap solution is also O(n log k) and can be more natural when lists arrive as streams or when you want to always expose the next global minimum.

Pairwise merging is often simpler when you already have a trusted mergeTwoLists helper and all lists are available upfront.

Pattern 4: Quad tree partitioning

Problem shape

You have an n x n binary grid. A quad tree compresses it by representing uniform square regions as leaves.

If a region is all zero or all one, it becomes a leaf. Otherwise, it splits into four equal quadrants.

Recursive contract

build(r0, c0, size) returns the node representing exactly this square:
rows r0..r0+size-1
cols c0..c0+size-1

Base case

The strongest base case is not only size == 1. Any uniform region can stop:

if all values in region are 0: return leaf(false)
if all values in region are 1: return leaf(true)

This is compression. A 64 x 64 all-ones grid should be one leaf, not thousands of tiny leaves.

Split

For half = size / 2:

TopLeft:     (r0,      c0,      half)
TopRight:    (r0,      c0+half, half)
BottomLeft:  (r0+half, c0,      half)
BottomRight: (r0+half, c0+half, half)

A simple coordinate mistake here produces a tree that looks structurally valid but represents the wrong image.

Uniformity check: simple scan versus prefix sum

The simplest implementation scans every cell in the current region.

That is fine for small constraints, but the professional upgrade is to build a 2D prefix sum. Then you can get the number of ones in any square in O(1).

sum = number of ones in region
area = size * size

sum == 0     => all zero
sum == area  => all one
otherwise    => mixed

This turns uniformity from repeated scanning into constant-time region queries.

Walkthrough

Grid:

1 1 0 0
1 1 0 0
1 0 0 0
1 0 0 1

Root region is mixed, so split into four 2 x 2 quadrants:

TopLeft:
1 1
1 1
=> leaf true

TopRight:
0 0
0 0
=> leaf false

BottomLeft:
1 0
1 0
=> mixed, split again

BottomRight:
0 0
0 1
=> mixed, split again

The final tree preserves the full grid but compresses the uniform top quadrants.

Correctness proof

For any call build(r0,c0,size), if the region is uniform, a leaf with that value exactly represents the region.

If the region is mixed, the four child calls cover the region exactly, without overlap and without gaps. By induction, each child correctly represents its quadrant. A non-leaf node with those four children therefore correctly represents the whole region.

Complexity

With naive scanning, worst-case time is O(n^2 log n) because each level of the quad tree can scan a total of O(n^2) cells.

With prefix sums, preprocessing is O(n^2). Each node checks uniformity in O(1). The number of quad-tree nodes is O(n^2) in the worst case, so total time is O(n^2).

Recursion depth is O(log n).

Failure modes

Do not rely on Val for non-leaf nodes. The value is irrelevant when IsLeaf is false.

Do not scan only the first row or first column. Uniformity means the entire square.

Do not create children for a leaf.

How to recognize divide-and-conquer in interviews

Use divide-and-conquer when the prompt has one or more of these signals:

• “sorted input” and you need a balanced tree or logarithmic-depth structure.
• “merge many sorted things.”
• “sort a linked list” under O(n log n) constraints.
• “compress a grid/image/region.”
• “compute result for a range from left half and right half.”
• “subproblems are independent after choosing a split.”

Be skeptical when:

• subproblems overlap heavily;
• children need shared mutable state;
• the combine step is harder than the original problem;
• a heap, stack, or two-pointer solution gives a simpler direct path.

The professional proof template

Most divide-and-conquer proofs can use this structure:

Contract:
  build(x) returns [precise result] for [precise boundary].

Base case:
  For the smallest boundary, the algorithm returns the correct direct result.

Induction hypothesis:
  Assume recursive calls return correct results for smaller boundaries.

Inductive step:
  The split covers the parent boundary exactly.
  The recursive calls solve each child boundary by the hypothesis.
  The combine step creates exactly the parent result from child results.

Termination:
  Every recursive call receives a strictly smaller boundary.

For linked lists, add:

The split produces disjoint lists.
The merge appends every original node exactly once.

For grids, add:

The four quadrants cover the square exactly, with no overlap and no gaps.

Debugging divide-and-conquer

When your solution fails, print or inspect the boundaries, not only values.

For arrays:

build(lo=0, hi=4)
build(lo=0, hi=1)
build(lo=0, hi=-1)
build(lo=1, hi=1)

For linked lists, temporarily convert each segment to a small slice after splitting. If both halves still show the same tail nodes, you forgot to cut.

For grids, log (r0, c0, size) and verify the four children:

(r0,c0,h)
(r0,c0+h,h)
(r0+h,c0,h)
(r0+h,c0+h,h)

If a recursive solution times out, ask whether the same elements are being repeatedly scanned at every level. Quad tree uniformity is the example in this module.

Problem map

Mastery ladder

Level 1: Can trace

You can draw the recursion tree for a small input and identify base cases.

Level 2: Can implement

You can write the solution without off-by-one errors, pointer cycles, or lost nodes.

Level 3: Can prove

You can state the contract and prove it by induction.

Level 4: Can optimize

You can recognize repeated work and introduce a better combine or preprocessing step, such as prefix sums for quad trees.

Level 5: Can choose alternatives

You can explain when to use a heap instead of pairwise merging, or DP instead of divide-and-conquer.

Minimum implementation discipline

For every problem in this module, your implementation should pass these property checks, not just sample cases:

• The result contains all input data and no extra data.
• The structural property is true: balanced BST, sorted list, valid quad tree.
• Edge cases work: empty input, one item, odd sizes, duplicates where allowed.
• The algorithm has the promised asymptotic behavior.
• Pointer-based solutions do not create cycles.