0 questions using this pattern
Break a problem into smaller subproblems, solve them independently, and combine results. Unlike DP, subproblems don't overlap.
Imagine sorting a deck of cards by splitting it in half, having two friends each sort their half, then merging the sorted halves. Each friend can recursively split their half too. The key: halves are independent and combining sorted halves is easy.
Three steps:
Time complexity often follows: T(n) = aT(n/b) + O(n^c) Solved by Master Theorem.
Use this skeleton as a starting point for problems using this pattern:
def merge_sort(arr: list[int]) -> list[int]:
"""Classic divide and conquer example."""
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# Combine (merge)
return merge(left, right)
def merge(left: list[int], right: list[int]) -> list[int]:
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return resultLook for these keywords and patterns in problem descriptions:
D&C subproblems are independent. DP subproblems overlap and need memoization. Using D&C on overlapping subproblems causes exponential time.
Fix:
Check: Do subproblems share computation? If yes, use DP. If no, use D&C.
If combining takes O(n^2), overall might not be better than brute force.
Fix:
Design O(n) or O(n log n) combine step. Merge sort's merge is O(n).
Sort by splitting, sorting halves, merging
Examples: sort-an-array
Find kth element by partitioning
Examples: kth-largest-element-in-an-array
Count pairs where larger element precedes smaller
Examples: count-of-smaller-numbers-after-self
Explore similar techniques:
Efficiently search sorted data by repeatedly dividing the search space in half. This transforms O(n) linear search into O(log n) by eliminating half the remaining possibilities with each comparison.
Break problems into overlapping subproblems, storing results to avoid recomputation. This transforms exponential time complexity into polynomial by trading space for time.