Divide & Conquer

Divide and conquer splits a problem into independent subproblems, solves them recursively, then combines results. The invariant is that each subproblem boundary is correct.

Pattern A: Balanced BST from sorted array

Use when: you need a height-balanced BST from sorted data.

Invariant: choosing the middle element yields balanced subtrees.

Skeleton:

func build(lo, hi):
    if lo > hi: return nil
    mid = (lo + hi) / 2
    root = new Node(nums[mid])
    root.left = build(lo, mid-1)
    root.right = build(mid+1, hi)
    return root

Problems:

• convert-sorted-array-to-binary-search-tree.

Pattern B: Merge sort on linked list

Use when: you need O(n log n) sort without extra arrays.

Invariant: slow/fast split produces two halves.

Skeleton:

func sort(head):
    if head == nil or head.next == nil: return head
    mid = split(head)
    left = sort(head)
    right = sort(mid)
    return merge(left, right)

Problems:

• sort-list.

Pattern C: Merge k lists by divide and conquer

Use when: you need to merge many sorted lists efficiently.

Invariant: merge pairs reduces k lists to k/2 lists each round.

Skeleton:

func mergeK(lists):
    if empty: return nil
    while len(lists) > 1:
        merged = []
        for i in 0..len-1 step 2:
            merged.append(merge(lists[i], lists[i+1]))
        lists = merged
    return lists[0]

Problems:

• merge-k-sorted-lists.

Pattern D: Quad tree partitioning

Use when: you must compress a grid into uniform quadrants.

Invariant: a node is a leaf if all cells in its region are equal.

Skeleton:

func build(r0,c0,size):
    if region is uniform: return leaf
    half = size/2
    return node(
        build(r0,c0,half),
        build(r0,c0+half,half),
        build(r0+half,c0,half),
        build(r0+half,c0+half,half),
    )

Problems:

• construct-quad-tree.

When to use Divide & Conquer (checklist)

• The problem splits into independent subproblems.
• Combining subproblem results is straightforward.

Common failures (checklist)

• Off-by-one errors in split boundaries.
• Failing to define a correct base case.
• Combining results in the wrong order.

Problem mapping

• convert-sorted-array-to-binary-search-tree: mid split.
• sort-list: merge sort with slow/fast split.
• merge-k-sorted-lists: pairwise merging.
• construct-quad-tree: recursive quadrant partition.