Divide and Conquer

Divide and conquer has three steps, and only one of them is interesting:

Divide the problem into independent subproblems — usually trivial.
Conquer each recursively — also trivial, it is just a recursive call.
Combine the results — this is the algorithm.

Merge sort is not interesting because it splits in half; it is interesting because of mergemerge. And the reason the pattern is worth its own page is that the combine step can compute things far beyond the stated problem: while merging two sorted halves, you can count cross-half relationships for free, which turns several $O(n^2)$ problems into $O(n \log n)$ .

What you’ll learn

The three-step skeleton, and how to reason about its cost with the Master Theorem.
Why merge sort counts things — the technique behind inversion counting.
Divide and conquer on expressions rather than arrays, where the split point is a choice.
When D&C is the wrong tool, and what to use instead.
Three real LeetCode problems solved in the browser: 912, 241, 493.

The cue

The skeleton

divide_conquer.py

def solve(problem):
    if is_base_case(problem):          # small enough to answer directly
        return answer(problem)
 
    left, right = split(problem)       # 1. DIVIDE
    left_result = solve(left)          # 2. CONQUER
    right_result = solve(right)
 
    return combine(left_result, right_result)   # 3. COMBINE -- the real work

divide_conquer.py

def solve(problem):
    if is_base_case(problem):          # small enough to answer directly
        return answer(problem)
 
    left, right = split(problem)       # 1. DIVIDE
    left_result = solve(left)          # 2. CONQUER
    right_result = solve(right)
 
    return combine(left_result, right_result)   # 3. COMBINE -- the real work

Reasoning about the cost

The Master Theorem gives the complexity from the recurrence $T(n) = a \cdot T(n/b) + f(n)$ , where aa is the number of subproblems, bb the shrink factor, and f(n)f(n) the cost of combining.

Algorithm	Recurrence	Result
Binary search	$T(n) = T(n/2) + O(1)$	$O(\log n)$
Merge sort	$T(n) = 2T(n/2) + O(n)$	$O(n \log n)$
Naive matrix multiply	$T(n) = 8T(n/2) + O(n^2)$	$O(n^3)$
Strassen	$T(n) = 7T(n/2) + O(n^2)$	$O(n^{2.807})$

Strassen is instructive: it changes only aa, from 8 subproblems to 7, and that alone beats the textbook cubic bound. When you want a D&C algorithm to be faster, you either reduce the number of subproblems or cheapen the combine.

Merge sort, and its real value

merge_sort.py

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
 
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:            # <= keeps the sort STABLE
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])                   # one side may remain
    out.extend(right[j:])
    return out

merge_sort.py

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
 
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:            # <= keeps the sort STABLE
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])                   # one side may remain
    out.extend(right[j:])
    return out

$O(n \log n)$ time and $O(n)$ space, and stable thanks to the <=<=.

Counting during the merge

Here is the idea worth taking from this page. When merging sorted leftleft and sorted rightright, if left[i] > 2 * right[j]left[i] > 2 * right[j], then every remaining element of leftleft also exceeds 2 * right[j]2 * right[j], because leftleft is sorted ascending.

So instead of checking pairs one at a time, you count them in blocks:

count_during_merge.py

def count_reverse_pairs(a):
    """Count pairs i < j with a[i] > 2 * a[j]."""
    def sort_count(a):
        if len(a) <= 1:
            return a, 0
        mid = len(a) // 2
        left, cl = sort_count(a[:mid])
        right, cr = sort_count(a[mid:])
        count = cl + cr
 
        j = 0                              # a pointer that NEVER resets
        for x in left:                     # both halves are sorted here
            while j < len(right) and x > 2 * right[j]:
                j += 1
            count += j                     # x beats the first j elements
 
        merged, i, k = [], 0, 0            # then merge as usual
        while i < len(left) and k < len(right):
            if left[i] <= right[k]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[k]); k += 1
        merged.extend(left[i:]); merged.extend(right[k:])
        return merged, count
 
    return sort_count(a)[1]

count_during_merge.py

def count_reverse_pairs(a):
    """Count pairs i < j with a[i] > 2 * a[j]."""
    def sort_count(a):
        if len(a) <= 1:
            return a, 0
        mid = len(a) // 2
        left, cl = sort_count(a[:mid])
        right, cr = sort_count(a[mid:])
        count = cl + cr
 
        j = 0                              # a pointer that NEVER resets
        for x in left:                     # both halves are sorted here
            while j < len(right) and x > 2 * right[j]:
                j += 1
            count += j                     # x beats the first j elements
 
        merged, i, k = [], 0, 0            # then merge as usual
        while i < len(left) and k < len(right):
            if left[i] <= right[k]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[k]); k += 1
        merged.extend(left[i:]); merged.extend(right[k:])
        return merged, count
 
    return sort_count(a)[1]

Every pair (i, j)(i, j) with ii in the left half and jj in the right half is counted exactly once, at the merge that first separates them. Pairs within a half are counted by the recursive calls. So every pair is accounted for exactly once, which is why the total is correct.

Divide and conquer on expressions

For LC 241 the split point is not the midpoint — it is every operator in turn, and each choice yields a different set of results:

diff_ways_to_compute.py

from functools import lru_cache
 
 
def diff_ways_to_compute(expression):
    @lru_cache(maxsize=None)               # memoise: substrings recur a lot
    def solve(expr):
        if expr.lstrip("-").isdigit():     # base case: a bare number
            return (int(expr),)
 
        results = []
        for i, ch in enumerate(expr):
            if ch in "+-*":
                for a in solve(expr[:i]):          # every left result
                    for b in solve(expr[i + 1:]):  # crossed with every right
                        results.append(a + b if ch == "+" else
                                       a - b if ch == "-" else a * b)
        return tuple(results)
 
    return list(solve(expression))

diff_ways_to_compute.py

from functools import lru_cache
 
 
def diff_ways_to_compute(expression):
    @lru_cache(maxsize=None)               # memoise: substrings recur a lot
    def solve(expr):
        if expr.lstrip("-").isdigit():     # base case: a bare number
            return (int(expr),)
 
        results = []
        for i, ch in enumerate(expr):
            if ch in "+-*":
                for a in solve(expr[:i]):          # every left result
                    for b in solve(expr[i + 1:]):  # crossed with every right
                        results.append(a + b if ch == "+" else
                                       a - b if ch == "-" else a * b)
        return tuple(results)
 
    return list(solve(expression))

The combine step is a cross product: every result from the left combined with every result from the right. That is characteristic of “all possible ways” problems.

The same substrings recur across different split choices, so lru_cachelru_cache turns exponential recomputation into something manageable. Note the function must return a tuple, not a list, because lru_cachelru_cache requires hashable return values only in the sense that arguments must be hashable — but returning an immutable tuple also prevents a caller mutating the cached value, which would corrupt later lookups. Returning a mutable list from a cached function is a genuine and subtle bug.

Also note expr.lstrip("-").isdigit()expr.lstrip("-").isdigit() rather than expr.isdigit()expr.isdigit(): the latter is FalseFalse for a negative number, which can appear once you allow expressions with leading minus signs. LC 241’s inputs are non-negative, but the guard costs nothing and is correct in general.

The variant map

Variant	The combine step	Canonical problem
Sort	Merge two sorted halves	912 · 148
Count cross-half pairs	Count during the merge	493 · 315 · 327
All possible results	Cross product of both sides	241 · 95
Best of left, right, or crossing	Compare three candidates	53 (D&C variant) · 1763
Discard half of one input	Binary search on the split position	4 Median of Two Sorted Arrays
Closest pair of points	Check the strip near the dividing line	classic geometry

Median of Two Sorted Arrays in $O(\log(m+n))$ is not really “split the arrays” — it is binary search on how many elements of the smaller array belong to the left partition.

Choose ii elements from nums1nums1 and j = half - ij = half - i from nums2nums2. The partition is correct when nums1[i-1] <= nums2[j]nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i]nums2[j-1] <= nums1[i] — both halves are then correctly separated, and the median comes from the boundary values. Binary search ii, always over the shorter array so the range is small and jj stays in bounds.

The reframe — from “divide the arrays” to “search for the split point” — is what makes it tractable. Also worth saying: the $O(m+n)$ merge-until-the-middle solution is far easier and is often accepted.

Practice — real LeetCode problems

LC 912 — Sort an Array · Medium

Problem. Sort an array of integers ascending. You must not use any built-in sorting function, and the solution should be $O(n \log n)$ with the lowest possible space complexity.

Constraints. 1 <= len(nums) <= 5 * 10^41 <= len(nums) <= 5 * 10^4, -5 * 10^4 <= nums[i] <= 5 * 10^4-5 * 10^4 <= nums[i] <= 5 * 10^4.

Examples. [5,2,3,1][5,2,3,1] gives [1,2,3,5][1,2,3,5] · [5,1,1,2,0,0][5,1,1,2,0,0] gives [0,0,1,1,2,5][0,0,1,1,2,5]

Editorial — approach, complexity, follow-ups

Split in half, sort each half, merge. The merge walks both halves once, always taking the smaller front element.

Time $O(n \log n)$ — $\log n$ levels, $O(n)$ merging per level. Space $O(n)$ for the temporary lists, plus $O(\log n)$ recursion.

<=<= rather than << makes the sort stable: equal elements keep their relative order. It makes no visible difference for plain integers, but it matters the moment you sort records by a key, and it is the correct default. LeetCode’s own [5,1,1,2,0,0][5,1,1,2,0,0] example contains duplicates specifically to exercise the merge.

Note this problem explicitly asks for “the smallest space complexity possible”, which is a nudge toward heap sort ( $O(1)$ extra space) or an in-place quicksort with a randomised pivot. Worth mentioning both:

Quicksort is $O(n \log n)$ average and $O(1)$ extra, but $O(n^2)$ worst case — and LC 912 has adversarial tests that kill a fixed pivot, so randomise.
Heap sort is $O(n \log n)$ worst case and $O(1)$ extra, but not stable.

Merge sort is the safe answer for a D&C discussion; naming the trade-offs is what makes it a complete one. See Merge Sort and Quick Sort.

Follow-ups you should expect: “Sort a linked list (LC 148)?” — merge sort is the natural fit, since splitting needs no random access; find the middle with fast/slow pointers and merge with a dummy head. “Do it in place?” — in-place merging is possible but fiddly and slower; prefer heap sort if $O(1)$ space is required. “Why does Python’s sortedsorted use Timsort?” — it exploits existing runs in real data, giving $O(n)$ on nearly-sorted input.

LC 241 — Different Ways to Add Parentheses · Medium

Problem. Given a string expressionexpression of numbers and the operators ++, -- and **, return all possible results from computing it with every valid parenthesisation. Results may be returned in any order.

Constraints. 1 <= len(expression) <= 201 <= len(expression) <= 20, non-negative integers under 10, and the number of results does not exceed 10^410^4.

Examples. "2-1-1""2-1-1" gives [0, 2][0, 2] · "2*3-4*5""2*3-4*5" gives [-34,-14,-10,-10,10][-34,-14,-10,-10,10] (note the repeated -10-10) · "11""11" gives [11][11]

Editorial — approach, complexity, follow-ups

Each operator is a candidate root of the expression tree. Choosing it splits the string into a left and a right subexpression, each of which has its own set of possible values. The results for this choice are every left value combined with every right value.

Time exponential in general — the count of distinct parenthesisations follows the Catalan numbers — but bounded here by the promise of at most $10^4$ results, and cut substantially by memoisation. Space $O(\text{results})$ plus the cache.

Two details:

"11""11" must give [11][11]. The base case has to handle multi-digit numbers, so it tests the whole substring rather than a single character. isdigit()isdigit() on the string does that.
Do not deduplicate. "2*3-4*5""2*3-4*5" yields -10-10 from two different parenthesisations and the expected output lists it twice. Wrapping the result in a setset is a plausible-looking mistake that fails this exact example.

Returning a tuple from the memoised function is deliberate: a cached mutable list could be modified by a caller and corrupt every later lookup.

Without memoisation this is still accepted at len <= 20len <= 20, so it is optional here — but recognising that the subproblems overlap is the observation that connects D&C to dynamic programming. When they overlap heavily, memoising is what stops D&C from being exponential.

Follow-ups you should expect: “Return the expressions, not just the values?” — build strings alongside the numbers in the combine step. “Handle division?” — add the operator and guard against dividing by zero. “Count the ways rather than list them?” — the nn-th Catalan number over the operator count, no enumeration needed. “Generate all BSTs from 1..n1..n (LC 95)?” — structurally identical: each value is a candidate root, and the combine is a cross product of left and right subtrees.

LC 493 — Reverse Pairs · Hard

Problem. A reverse pair is a pair (i, j)(i, j) with i < ji < j and nums[i] > 2 * nums[j]nums[i] > 2 * nums[j]. Return the number of reverse pairs.

Constraints. 1 <= len(nums) <= 5 * 10^41 <= len(nums) <= 5 * 10^4, -2^31 <= nums[i] <= 2^31 - 1-2^31 <= nums[i] <= 2^31 - 1.

Examples. [1,3,2,3,1][1,3,2,3,1] gives 22 · [2,4,3,5,1][2,4,3,5,1] gives 33 · [5,4,3,2,1][5,4,3,2,1] gives 44

Editorial — approach, complexity, follow-ups

Every reverse pair has its two indices either within one half or across the split. Recursion handles the within-half pairs; the merge step counts the cross-half ones. So every pair is counted exactly once, at the level where the two indices first end up in different halves.

The counting is cheap because both halves are already sorted: for ascending xx from leftleft, the set of qualifying rightright elements only grows, so one forward-only pointer suffices.

Time $O(n \log n)$ — the counting adds $O(n)$ per merge level, the same order as the merge itself. Space $O(n)$ .

Two details that decide whether this works:

jj outside the loop. Resetting it makes the count step $O(n^2)$ and the whole thing $O(n^2 \log n)$ — worse than brute force. The amortised forward-only-pointer argument is the same one behind sliding window.
Count before merging. The counting loop relies on leftleft and rightright being separate sorted lists. Once merged, the split information is gone.

Test-case notes: [5,4,3,2,1][5,4,3,2,1] gives 44 — pairs (5,2)(5,2), (5,1)(5,1), (4,1)(4,1), (3,1)(3,1), since e.g. 5 > 2*25 > 2*2. [1,1,1][1,1,1] gives 00, confirming the strict inequality. And note the constraints allow the full 32-bit range, so 2 * nums[j]2 * nums[j] can exceed 32 bits — a non-issue in Python, but in C++ or Java you would need a 64-bit cast, which is a good detail to raise.

Follow-ups you should expect:

“Count plain inversions (nums[i] > nums[j]nums[i] > nums[j])?” The same algorithm with the factor of 2 removed — the classic inversion count.
“Count of smaller numbers after self (LC 315)?” Same merge-sort-with-counting idea, but you must track original indices to attribute counts per element.
“Do it with a Fenwick tree instead?” Yes: compress the values and query prefix counts as you sweep right to left. $O(n \log n)$ too, and often easier to extend. Worth naming as the alternative.
“Why not brute force?” $O(n^2)$ is $2.5 \times 10^9$ operations at $n = 5 \times 10^4$ — far too slow.

LeetCode problem set

#	Problem	Difficulty	The twist
912	Sort an Array	Medium	Merge sort; `<=<=` for stability
148	Sort List	Medium	Merge sort on a linked list — no random access needed
241	Different Ways to Add Parentheses	Medium	Split at every operator; combine is a cross product; do not deduplicate
493	Reverse Pairs	Hard	Count during the merge with a non-resetting pointer
315	Count of Smaller Numbers After Self	Hard	Same idea, but attribute counts to original indices
4	Median of Two Sorted Arrays	Hard	Binary search the split position in the shorter array

Interview follow-ups

They ask	What they’re checking	The answer
“Where is the actual work?”	Understanding the pattern	In the combine step; divide and conquer are usually trivial
“Derive the complexity”	Master Theorem fluency	$T(n) = aT(n/b) + f(n)$ ; merge sort is $2T(n/2) + O(n) = O(n \log n)$
“How does merge sort count inversions?”	The key technique	Cross-half pairs are counted at the merge with a forward-only pointer, so $O(n)$ per level
“Why must the pointer not reset?”	Amortised reasoning	Both halves are sorted, so it only moves forward — resetting makes the step $O(n^2)$
“What if the subproblems overlap?”	Knowing the boundary	Plain D&C recomputes exponentially; memoise, i.e. use DP
“Merge sort or quicksort?”	Judgement	Merge for stability, predictable splits and linked lists; quicksort for $O(1)$ space in-place, with a randomised pivot
“Alternative to merge-counting?”	Breadth	A Fenwick tree over compressed values, sweeping from the right

Edge-case checklist

Single element — the base case for every recursion here.
Empty input — guard len(a) <= 1len(a) <= 1 covers it.
All identical — [3,3,3][3,3,3] sorts fine and yields 00 reverse pairs (strict inequality).
Already sorted / reverse sorted — the extremes for counting; [5,4,3,2,1][5,4,3,2,1] gives 4.
Negative values — legal in 912 and 493; 2 * nums[j]2 * nums[j] gets smaller for negatives, so do not assume monotonic behaviour.
32-bit overflow in 2 * nums[j]2 * nums[j] — a non-issue in Python, real elsewhere.
Multi-digit numbers (LC 241) — "11""11" must parse as one number.
Duplicate results (LC 241) — must be kept, not deduplicated.
Recursion depth — $\log n$ for merge sort, so never a problem; but expression recursion is bounded by string length.

Recap

Divide and conquer is split, solve, combine — and the combine step is the algorithm.
Use the Master Theorem to get the complexity from the recurrence; to speed a D&C algorithm up, reduce the number of subproblems or cheapen the combine.
Merge sort counts things. Cross-half relationships can be tallied during the merge in $O(n)$ per level, turning $O(n^2)$ pair-counting into $O(n \log n)$ . The counting pointer must never reset.
Every pair is counted exactly once — at the level where its indices first fall into different halves.
For “all possible ways” problems, split at every valid point and make the combine a cross product. Memoise when substrings recur.
If subproblems overlap, plain D&C is exponential — that is DP’s territory.
<=<= in the merge keeps the sort stable.

Next: the dynamic programming phase — what to do when the subproblems overlap.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Divide and Conquer

What you’ll learn

The cue

The skeleton

Reasoning about the cost

Merge sort, and its real value

Counting during the merge

Divide and conquer on expressions

The variant map

Practice — real LeetCode problems

LC 912 — Sort an Array · Medium

LC 241 — Different Ways to Add Parentheses · Medium

LC 493 — Reverse Pairs · Hard

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?