Divide and Conquer

Key idea — Like tree recursion, but the split is deliberate: break the input into independent (non-overlapping) halves, recurse on each, then merge the results. Unlike DP, sub-problems do not overlap so no caching is needed.

When to use — Merge sort, quick sort, binary search, "find maximum sub-array" (Kadane can also apply), closest pair of points, matrix exponentiation. Cue: "split input, solve left half and right half independently, combine."

Pattern / template

func solve(arr []int, lo, hi int) int {
    // Base case
    if lo >= hi {
        return baseAnswer(arr[lo])
    }

    mid := lo + (hi-lo)/2

    left := solve(arr, lo, mid)     // solve left half
    right := solve(arr, mid+1, hi)  // solve right half

    return merge(left, right) // combine
}

Merge sort is the canonical example — merge takes O(n) and recurrence is T(n) = 2T(n/2) + O(n) → O(n log n).

Complexity

• Master theorem: T(n) = aT(n/b) + f(n).
• Typical (a=2, b=2, f=O(n)): O(n log n).
• Space: O(log n) call stack; merge sort needs O(n) auxiliary space.

Pitfalls

• Forgetting to handle the base case for a single element vs empty range.
• Off-by-one in mid calculation — use lo + (hi-lo)/2 to avoid integer overflow.
• Merge step must handle both halves being fully consumed before the loop exits.

Common follow-ups

• What does the Master Theorem tell you about the recurrence T(n) = 2T(n/2) + O(n)?
• How does quick sort differ from merge sort in terms of when the work happens (split vs merge)?
• When would you prefer divide-and-conquer over DP, and what distinguishes the two?
• How do you implement in-place merge sort to avoid the O(n) auxiliary space?

Practice (LeetCode)

• LC 912 — Sort an Array
• LC 53 — Maximum Subarray
• LC 215 — Kth Largest Element in an Array
• LC 169 — Majority Element
• LC 23 — Merge k Sorted Lists