Divide and Conquer Template
Extract the three-step template (divide, conquer, combine) from merge sort and apply it systematically to new problem shapes.
What is Divide and Conquer?
Divide and Conquer (D&C) solves a problem by breaking it into independent sub-problems of the same type, solving each recursively, and combining their solutions. The key word is independent — sub-problems do not share state (unlike DP where they overlap). Classic examples: merge sort, binary search, quick sort, closest pair of points, and fast matrix multiplication. D&C typically achieves O(n log n) time through the three-step template.
# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP: sub-problems OVERLAP (same sub-problem solved multiple times)
# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing
# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n) [merge sort]
# T(n) = T(n/2) + O(1) → O(log n) [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]The Three-Step Template
Every D&C algorithm follows three steps: (1) Divide — split the problem into two (or more) smaller sub-problems, typically at the midpoint. (2) Conquer — recursively solve each sub-problem. Define a base case to stop recursion (usually n ≤ 1). (3) Combine — merge or combine the sub-problem solutions into the overall solution. The creativity lies entirely in the Combine step; Divide is usually just splitting at the midpoint.
def divide_and_conquer(arr, lo, hi):
# BASE CASE: trivial sub-problem
if lo >= hi:
return base_case_result(arr, lo, hi)
# DIVIDE: split at midpoint
mid = (lo + hi) // 2
# CONQUER: solve sub-problems recursively
left_result = divide_and_conquer(arr, lo, mid)
right_result = divide_and_conquer(arr, mid + 1, hi)
# COMBINE: merge results
return combine(left_result, right_result, arr, lo, mid, hi)
def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)All lessons in this course
- Divide and Conquer Template
- Count Inversions Using Modified Merge Sort
- Majority Element: Boyer-Moore Voting
- Median of Two Sorted Arrays