Divide and Conquer

Core Concepts

Divide and Conquer — a recursive paradigm: split the input into independent subproblems of the same form, solve each recursively, then combine the results. Correctness depends on the combine (merge) step correctly aggregating partial answers.

Subproblem independence — subproblems operate on disjoint portions of the input and do not share state. This distinguishes D&C from DP, where subproblems overlap; when overlap is present, memoization is required.

Recurrence relation — describes runtime: T(n) = aT(n/b) + f(n), where a = number of subproblems, b = factor by which input shrinks, f(n) = cost of the divide and merge steps.

Base case — the stopping condition; must be reached in finite steps and resolved in O(1) or trivially.

Merge step — the logic applied after recursive calls return. Almost always where the hard work lives; the split is usually O(1) or O(n).

Master Theorem — closed-form for T(n) = aT(n/b) + O(n^d): if d > log_b(a) → O(n^d); if d = log_b(a) → O(n^d log n); if d < log_b(a) → O(n^(log_b a)).

Decrease and conquer — a=1 variant: a single subproblem of size n/b is solved; the other portion is eliminated by an invariant. Binary search is the canonical example.

Types / Variants

Key Algorithms

Merge Sort

Splits array at midpoint, recursively sorts both halves, merges the two sorted halves. Key insight: merging two sorted arrays is O(n); balanced splitting ensures log n levels. T(n) = 2T(n/2) + O(n) → O(n log n) time, O(n) space (merge buffer).

See sorting.md for full merge sort, quicksort, and variant coverage.

Counting Inversions

Augments the merge step of merge sort: when a right-half element is placed before a left-half element, add mid - left_ptr + 1 inversions (all remaining left elements are larger). No extra passes needed; total cost stays O(n log n).

Binary Search

Eliminates half the search space per step by comparing the midpoint value to the target or predicate. T(n) = T(n/2) + O(1) → O(log n). Prerequisite: the predicate must be monotone (all False then all True, or vice versa).

Fast Exponentiation (Exponentiation by Squaring)

Computes x^n in O(log n) by halving: x^n = (x²)^(n//2) when n is even; x · x^(n−1) when n is odd.

return (x*x)**(n//2) * (x if n%2 else 1)

Maximum Subarray (D&C version)

Splits at midpoint. Answer is the max of: (1) best subarray in the left half, (2) best subarray in the right half, (3) best subarray crossing the midpoint. The crossing case expands greedily left and right from mid in O(n). T(n) = 2T(n/2) + O(n) → O(n log n). Note: Kadane's algorithm solves this in O(n); the D&C version is practiced for the paradigm, not for efficiency.

Closest Pair of Points

Sorts points by x-coordinate. Splits at the median x-value. Recursively finds δ = min closest-pair distance in each half. Merge step: only examine points within δ of the dividing line, sorted by y — by geometry, at most 7 points need checking per point in the strip. T(n) = 2T(n/2) + O(n log n) → O(n log² n); pre-sorting by y before recursion reduces to O(n log n).

Quickselect

Partitions around a pivot and recurses only on the half containing the k-th element. O(n) average with random pivot; O(n²) worst case. Median-of-medians pivot selection guarantees O(n) worst case at higher constant cost.

See sorting.md for pivot strategies and quicksort coverage.

Karatsuba Multiplication

Multiplies two n-digit numbers in O(n^log₂3) ≈ O(n^1.585) vs. O(n²) schoolbook. Uses the identity: given a·10^m + b and c·10^m + d, compute only ac, bd, and (a+b)(c+d) — three multiplications recover all four cross-products. T(n) = 3T(n/2) + O(n) → O(n^log₂3).

Skyline Problem (Segment Merge)

Splits the building list in half, recursively computes the skyline for each half, then merges two skylines via a two-pointer scan tracking the current max height from each side. Same merge structure as merging sorted lists. O(n log n) total.

Advanced Techniques

Merge-Step Counting

Solves: counting pairs (i, j) where i < j and the pair satisfies an order-based condition detectable when elements from two sorted halves cross during merge — e.g., inversions, reverse pairs (arr[i] > 2·arr[j]), count of smaller numbers after self.

Mechanism: augment the merge loop to update a counter when an element from the right half is placed before elements remaining in the left half. Sortedness of each half is the invariant that makes counting O(n) per level rather than O(n²).

When to use over alternatives: only when the pair condition is expressible as an order comparison at merge time. For conditions that depend on value arithmetic not preserved by sorting order (e.g., sum of pair in a range), use a hash-based scan or sorted-container approach instead.

Complexity: O(n log n) time, O(n) space.

D&C on Query Space (Offline CDQ)

Solves: problems where queries over an index range [L, R] can be decomposed into: queries entirely in [L, mid], entirely in [mid+1, R], and those spanning mid. Cross-boundary contributions are computed in O(n) per merge level.

Mechanism: divide the problem's index (or time) range, recurse, handle cross-boundary contributions (e.g., updates in left half affecting queries in right half) in the combine step. Known as CDQ divide and conquer in competitive programming.

When to use over alternatives: when queries can be processed offline and a sweep handles cross-boundary contributions efficiently. For online queries requiring instant answers, use a persistent segment tree or BIT instead.

Complexity: O(n log n) with an O(n) combine step per level.

Problem Taxonomy

By Problem Category

Problem Signal → Technique

Common Patterns

Edge Cases & Pitfalls

• Off-by-one in midpoint: mid = lo + (hi - lo) // 2 prevents integer overflow in fixed-width languages; (lo + hi) // 2 overflows when lo + hi exceeds the type's maximum.
• Missing base case: always guard if lo >= hi: return before recursing; absent base cases cause infinite recursion or index errors on empty or single-element inputs.
• Incorrect inversion count: the formula mid - left_ptr + 1 is only valid when an element from the right half is consumed while the left pointer hasn't reached mid yet; confirm loop direction before applying the count.
• Wrong base case for fast power: x^0 = 1 must be explicit; if the recursion reaches n=0 and multiplies by x one extra time, all even-exponent results are wrong.
• Closest pair strip sort direction: the strip must be sorted by y-coordinate for the O(n) scan; sorting by x gives O(n log n) per merge level.
• Crossing subarray boundary: expand left all the way to lo and right all the way to hi; stopping one element short can miss the global optimum.
• Unbalanced recursion depth: balanced D&C on n = 10^5 produces ~17 levels (safe). Unbalanced splits (quicksort with a bad pivot) can reach O(n) depth, causing a stack overflow.

Implementation Notes

• Python's default recursion limit is 1000; for n > 500 with potentially unbalanced recursion (quicksort), call sys.setrecursionlimit or convert to an iterative stack.
• arr[lo:hi] creates an O(n) copy per call; always pass index bounds instead of slices to keep merge sort at O(n log n) rather than O(n² log n).
• Python's list.sort() (Timsort) is faster than a hand-rolled merge sort for all practical sorting needs; write the D&C version only when the merge step carries additional logic such as inversion counting.
• Inversion counts can reach n·(n−1)/2 ≈ 5×10^9 for n = 10^5; use a 64-bit integer (long in Java/C++); Python ints are arbitrary precision.
• In modular fast power, apply % mod at every multiplication to prevent intermediate values from growing unbounded before the final modulo.

Cross-Topic Relations

Interview Reference

Must-Know Problems

Merge Sort / Counting

• Implement merge sort from scratch
• Count of Inversions (classic; GFG / Striver sheet)
• Reverse Pairs — LeetCode 493
• Count of Smaller Numbers After Self — LeetCode 315

Search / Selection

• Binary Search — LeetCode 704
• Search in Rotated Sorted Array — LeetCode 33
• Kth Largest Element in an Array — LeetCode 215 (quickselect)
• Find Minimum in Rotated Sorted Array — LeetCode 153

Range / Expression

• Maximum Subarray — LeetCode 53 (D&C version)
• Different Ways to Add Parentheses — LeetCode 241
• Expression Add Operators — LeetCode 282

Math / Exponentiation

• Pow(x, n) — LeetCode 50
• Super Pow — LeetCode 372

Geometric / Structural

• The Skyline Problem — LeetCode 218
• Closest pair of points (classic; rarely appears verbatim on LeetCode)

Clarification Questions to Ask

• Counting problems: are pairs (i, j) ordered (i < j only) or unordered? Does i = j count?
• K-th element: 1-indexed or 0-indexed? Does "k-th largest" count duplicates or only distinct values?
• Exponentiation: can n be negative? Is the result modular?
• Subarray: must the subarray be non-empty? Can it span the whole array?
• Binary search on custom predicates: confirm the predicate is monotone before assuming binary search applies.

Common Interview Mistakes

• Writing mid = (lo + hi) / 2 in Java/C++ where overflow can occur; correct form is lo + (hi - lo) / 2.
• Slicing arrays in recursive calls (arr[:mid], arr[mid:]) in Python — functionally correct but O(n) per call, making merge sort O(n² log n).
• Omitting the lo >= hi base case, causing an infinite loop or index-out-of-bounds on empty or size-1 inputs.
• Miscounting inversions by applying mid - left_ptr + 1 in the wrong loop condition.
• Using D&C on an overlapping-subproblem problem (e.g., Fibonacci) without memoization — exponential time.
• Claiming quickselect is O(n) without noting it is O(n²) worst case; if guaranteed O(n) is required, median-of-medians must be mentioned.

Typical Follow-Up Escalations

• "Implement merge sort" → "Now count inversions while sorting" → "Now count reverse pairs where arr[i] > 2·arr[j]"
• "Find the k-th largest element" → "Now do it in O(n) worst case" (median-of-medians)
• "Maximum subarray" → "Now do it in O(n)" (Kadane's) → "Now for a circular array" (max of normal and n − min_subarray)
• "Binary search for a target" → "Search in a 2D matrix" → "Search in a rotated array with duplicates"
• "Pow(x, n)" → "Now compute it modulo m" → "Now matrix exponentiation for Fibonacci in O(log n)"