Divide and Conquer Interview Patterns

The Pattern

Divide and conquer splits a problem into independent subproblems, solves each recursively, and combines the results. Three steps: Divide (split input), Conquer (recurse), Combine (merge results). Key property: subproblems are independent. Master theorem determines time complexity.

Master Theorem

For recurrences T(n) = aT(n/b) + O(n^d):

• d > log_b(a): O(n^d) — combine step dominates
• d == log_b(a): O(n^d * log n) — balanced
• d < log_b(a): O(n^log_b(a)) — recursion dominates

Merge sort: a=2, b=2, d=1 → d == log_2(2) → O(n log n). Binary search: a=1, b=2, d=0 → O(log n).

Merge Sort

Divide array in half, sort each half, merge. Stable, O(n log n) always, O(n) space.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    return result + a[i:] + b[j:]

Merge sort enables counting inversions (LC 315, 493): during the merge step, when a right-side element is chosen before a left-side element, add len(a) – i to the inversion count.

Quick Select (Kth Largest, LC 215)

Find the kth largest element in average O(n) by partitioning around a pivot and recursing into only the relevant half.

import random
def findKthLargest(nums, k):
    def partition(lo, hi):
        pivot_idx = random.randint(lo, hi)
        nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
        pivot = nums[hi]
        store = lo
        for i in range(lo, hi):
            if nums[i] >= pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]
        return store
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        p = partition(lo, hi)
        if p == k - 1: return nums[p]
        elif p < k - 1: lo = p + 1
        else: hi = p - 1

Randomize pivot selection to avoid O(n^2) worst case on sorted input.

Count Inversions (LC 315, 493)

An inversion is a pair (i,j) where i < j but arr[i] > arr[j]. Use merge sort: when a right-side element is merged before all remaining left-side elements, add len(left) – i to the count.

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, lc = count_inversions(arr[:mid])
    right, rc = count_inversions(arr[mid:])
    merged, mc = merge_count(left, right)
    return merged, lc + rc + mc

def merge_count(a, b):
    result, count = [], 0
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i]  b[j]
            result.append(b[j]); j += 1
    return result + a[i:] + b[j:], count

Median of Two Sorted Arrays (LC 4)

O(log(min(m,n))) by binary searching on the smaller array’s partition point. For each candidate partition of the smaller array, determine the required partition of the larger array. Check if the partition is valid (left max <= right min on both sides). Eliminate half the smaller array on each step.

When to Use Divide and Conquer

• Sorting problems where a merge step adds information: count inversions, sort linked list (LC 148)
• Selection: kth largest (quickselect), median of medians
• Geometric: closest pair of points, skyline problem (LC 218)
• Mathematical: matrix exponentiation (Fibonacci in O(log n)), fast power
• When subproblems are truly independent (vs DP where they overlap)

Meta coding interviews test divide and conquer and merge sort patterns. See common questions for Meta interview: divide and conquer and sorting problems.

Google coding interviews frequently test divide and conquer patterns. See problems for Google interview: divide and conquer algorithm problems.

Apple coding interviews test divide and conquer and quickselect. See patterns for Apple interview: divide and conquer and sorting problems.