Divide and Conquer — Tech Epitome

Divide and Conquer

Split into independent halves, solve each, combine the results.

Medium2 problems

How do I recognise this pattern?

The input splits naturally into halves that do not interact.
Merge sort, quicksort, or binary-search-like structure.
A target complexity of O(n log n) is hinted at.
Counting pairs across a split — inversions, for example.
Tree problems where the answer combines results from both subtrees.

When it is the wrong tool

Subproblems overlap, in which case memoisation is needed and this becomes dynamic programming.
The combine step costs more than solving directly.
The split does not reduce the problem — recursing on n-1 is just recursion.

What is it?

Break the input into parts that can be solved independently, recurse on each, then merge the answers. Unlike dynamic programming the parts do not overlap, so nothing needs to be memoised. The interesting work is usually in the combine step.

The core idea

The recurrence T(n) = 2·T(n/2) + O(n) resolves to O(n log n). If your combine step is worse than linear, check whether the split is actually buying anything.

Template

The shape, not a solution. Adapt the condition and the state to the problem in front of you.

Python

1def merge_sort(nums):2    if len(nums) <= 1:3        return nums4 5    mid = len(nums) // 26    left = merge_sort(nums[:mid])7    right = merge_sort(nums[mid:])8    return merge(left, right)9 10 11def merge(left, right):12    """The combine step — where the real work of divide and conquer lives."""13    result = []14    i = j = 015 16    while i < len(left) and j < len(right):17        # '<=' rather than '<' keeps equal elements in their original18        # relative order, which is what makes the sort stable.19        if left[i] <= right[j]:20            result.append(left[i])21            i += 122        else:23            result.append(right[j])24            j += 125 26    result.extend(left[i:])27    result.extend(right[j:])28    return result

Common mistakes

A base case that does not shrink, producing infinite recursion on inputs of length 1.
Forgetting to append the remainder of whichever side was not exhausted.
Using `<` in the merge comparison and silently losing stability.
Slicing on every call in a language where slicing copies, adding a hidden O(n) per level.

Problems using Divide and Conquer

Status	Problem	Difficulty	Role
	Merge Sorted Feeds#114	Medium	Related
	Fast Modular Power#129	Medium	Primary