Divide & Conquer

The Mental Model

Divide and Conquer is the recursive halving strategy. Instead of solving a problem of size n directly, split it into smaller subproblems (usually halves), solve each recursively, and combine the results. The power comes from reducing O(n^2) to O(n log n). Analogy: Imagine you need to count a huge pile of coins. Instead of counting one by one (O(n)), you split the pile in half, ask two friends to each count their half, and add the results. Each friend does the same—splits their pile and delegates. At the bottom, someone has one coin and just says “1.” The work at each level is O(n) (combining), and there are O(log n) levels, giving O(n log n) total.

Pattern Recognition Signals:

Problem can be split into independent subproblems
Combining halves is cheaper than solving directly
“Merge” or “split” appears naturally
O(n log n) is needed but brute force is O(n²)

The D&C Template

ReturnType divideAndConquer(Array arr, int lo, int hi) {
    // Base case: single element or empty
    if (lo >= hi) {
        return baseResult(arr, lo);
    }
    
    // Divide
    int mid = lo + (hi - lo) / 2;
    
    // Conquer
    ReturnType leftResult = divideAndConquer(arr, lo, mid);
    ReturnType rightResult = divideAndConquer(arr, mid + 1, hi);
    
    // Combine
    return combine(leftResult, rightResult, arr, lo, mid, hi);
}

Pattern 1: Merge Sort

The classic D&C algorithm. Demonstrates the paradigm perfectly.

void merge(vector<int>& arr, int lo, int mid, int hi) {
    vector<int> temp(hi - lo + 1);
    int i = lo, j = mid + 1, k = 0;
    
    while (i <= mid && j <= hi) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= hi) temp[k++] = arr[j++];
    
    for (int i = lo; i <= hi; i++) {
        arr[i] = temp[i - lo];
    }
}

void mergeSort(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    
    int mid = lo + (hi - lo) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
}

Complexity Analysis:

Divide: O(1)
Conquer: 2 × T(n/2)
Combine: O(n)
Total: T(n) = 2T(n/2) + O(n) = O(n log n)

Pattern 2: Count Inversions

Problem: Count pairs (i, j) where i < j but arr[i] > arr[j]. Insight: Modified merge sort. During merge, when we pick from the right half, all remaining left elements form inversions with it. Why this works: After dividing and sorting each half, elements within each half are already sorted (no internal inversions left to count—they were counted in deeper recursive calls). The only inversions that remain are cross-boundary pairs: an element from the left half that is larger than an element from the right half. During the merge step, whenever we pick arr[j] from the right half because arr[j] < arr[i], all elements from arr[i] to arr[mid] are also greater than arr[j]—that is mid - i + 1 inversions in one shot.

long long mergeCount(vector<int>& arr, int lo, int mid, int hi) {
    vector<int> temp(hi - lo + 1);
    int i = lo, j = mid + 1, k = 0;
    long long inversions = 0;
    
    while (i <= mid && j <= hi) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];  // No inversion: left <= right
        } else {
            temp[k++] = arr[j++];
            // arr[j] < arr[i], and arr[i..mid] are all sorted,
            // so all of arr[i..mid] form inversions with arr[j]
            inversions += (mid - i + 1);
        }
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= hi) temp[k++] = arr[j++];
    
    for (int i = lo; i <= hi; i++) arr[i] = temp[i - lo];
    
    return inversions;
}

long long countInversions(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return 0;
    
    int mid = lo + (hi - lo) / 2;
    long long count = 0;
    
    count += countInversions(arr, lo, mid);
    count += countInversions(arr, mid + 1, hi);
    count += mergeCount(arr, lo, mid, hi);
    
    return count;
}

Codeforces Problems:

Problem	Rating	Link
Inversions	1300	CSES

Pattern 3: Maximum Subarray (Kadane Alternative)

Problem: Find contiguous subarray with maximum sum. D&C Approach: Max subarray is either entirely in left, entirely in right, or crosses the middle.

struct Result {
    long long maxSum;      // Maximum subarray sum
    long long prefixSum;   // Maximum prefix sum
    long long suffixSum;   // Maximum suffix sum
    long long totalSum;    // Total sum of segment
};

Result solve(vector<int>& arr, int lo, int hi) {
    if (lo == hi) {
        return {arr[lo], arr[lo], arr[lo], arr[lo]};
    }
    
    int mid = lo + (hi - lo) / 2;
    Result left = solve(arr, lo, mid);
    Result right = solve(arr, mid + 1, hi);
    
    Result combined;
    combined.totalSum = left.totalSum + right.totalSum;
    combined.prefixSum = max(left.prefixSum, left.totalSum + right.prefixSum);
    combined.suffixSum = max(right.suffixSum, right.totalSum + left.suffixSum);
    combined.maxSum = max({left.maxSum, right.maxSum, 
                           left.suffixSum + right.prefixSum});
    
    return combined;
}

Pattern 4: Closest Pair of Points

Problem: Given n points in 2D, find the pair with minimum distance. Brute Force: O(n²) - check all pairs. D&C Approach:

Sort by x-coordinate
Split into left and right halves
Recursively find closest pair in each half
Check pairs crossing the middle (the tricky part)

double closestPair(vector<Point>& points) {
    // Sort by x
    sort(points.begin(), points.end(), [](auto& a, auto& b) {
        return a.x < b.x;
    });
    
    return closest(points, 0, points.size() - 1);
}

double closest(vector<Point>& points, int lo, int hi) {
    if (hi - lo <= 2) {
        return bruteForce(points, lo, hi);
    }
    
    int mid = lo + (hi - lo) / 2;
    double midX = points[mid].x;
    
    double d = min(closest(points, lo, mid), 
                   closest(points, mid + 1, hi));
    
    // Collect points within d of the dividing line
    vector<Point> strip;
    for (int i = lo; i <= hi; i++) {
        if (abs(points[i].x - midX) < d) {
            strip.push_back(points[i]);
        }
    }
    
    // Sort strip by y and check nearby points
    sort(strip.begin(), strip.end(), [](auto& a, auto& b) {
        return a.y < b.y;
    });
    
    for (int i = 0; i < strip.size(); i++) {
        for (int j = i + 1; j < strip.size() && 
             strip[j].y - strip[i].y < d; j++) {
            d = min(d, distance(strip[i], strip[j]));
        }
    }
    
    return d;
}

Key Insight: In the strip, we only need to check O(1) points for each point (at most 7 points below any point within distance d). This is the non-obvious part that makes the algorithm O(n log n) instead of O(n^2). A geometric packing argument proves it: within a d x 2d rectangle, you can fit at most 8 points that are all at least d apart from each other.

Contest tip: Closest pair of points is a classic ICPC problem. In practice, you can also solve it by sorting by x-coordinate and checking a sliding window, or even by randomized approaches. But the D&C solution is the textbook approach and good to know for interviews.

Pattern 5: Quick Select (Kth Smallest)

Problem: Find kth smallest element in O(n) average time. Approach: Partition like quicksort, but only recurse into the relevant half. This is the “half-lazy quicksort” — you do one partition, then only explore the side containing the answer. Why it is O(n) on average: After partitioning, you discard roughly half the array. The work at each level sums to n + n/2 + n/4 + … = 2n = O(n). Compare to quicksort, which must recurse into both halves for O(n log n) total. Worst case: O(n^2) if the pivot is consistently the worst element (e.g., already sorted array with last-element pivot). Randomizing the pivot or using the “median of medians” algorithm guarantees O(n) worst case, but in CP the randomized version is almost always sufficient.

int partition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi];  // Choose last element as pivot
    int i = lo;           // i tracks the boundary of "elements <= pivot"
    
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            swap(arr[i], arr[j]);  // Move small element to left partition
            i++;
        }
    }
    
    swap(arr[i], arr[hi]);  // Place pivot at its correct sorted position
    return i;               // Pivot is now at index i
}

int quickSelect(vector<int>& arr, int lo, int hi, int k) {
    if (lo == hi) return arr[lo];  // Single element
    
    int pivotIndex = partition(arr, lo, hi);
    
    if (k == pivotIndex) {
        return arr[k];  // Pivot is the kth element
    } else if (k < pivotIndex) {
        return quickSelect(arr, lo, pivotIndex - 1, k);  // Answer is in left half
    } else {
        return quickSelect(arr, pivotIndex + 1, hi, k);  // Answer is in right half
    }
}

int findKthSmallest(vector<int>& arr, int k) {
    return quickSelect(arr, 0, arr.size() - 1, k - 1);  // Convert 1-indexed to 0-indexed
}

Average Time: O(n) (each level processes n, n/2, n/4, … which sums to 2n)

Contest tip: In practice, C++ STL’s nth_element uses a variant of quickselect and is O(n) average. Prefer nth_element(arr.begin(), arr.begin() + k, arr.end()) over writing your own — it is faster to type and well-optimized.

The Master Theorem

For recurrences of the form T(n) = aT(n/b) + f(n):

Case	Condition	Result
1	f(n) = O(n^c) where c < log_b(a)	T(n) = O(n^(log_b(a)))
2	f(n) = O(n^c) where c = log_b(a)	T(n) = O(n^c log n)
3	f(n) = O(n^c) where c > log_b(a)	T(n) = O(f(n))

Common Examples:

Merge Sort: T(n) = 2T(n/2) + O(n) → O(n log n)
Binary Search: T(n) = T(n/2) + O(1) → O(log n)
Strassen: T(n) = 7T(n/2) + O(n²) → O(n^2.81)

Common Mistakes

Mistake 1: Wrong Base Case

// WRONG: Infinite recursion when lo == hi
if (lo > hi) return;

// CORRECT
if (lo >= hi) return;

Mistake 2: Stack Overflow D&C depth is O(log n) for balanced splits, but O(n) for unbalanced (like quicksort worst case). Use iterative or randomized pivot.

Mistake 3: Inefficient Combine If combine is O(n²), you lose the benefit:

Good: O(n) combine → O(n log n) total
Bad: O(n²) combine → O(n² log n) total (worse than brute force!)

D&C vs Other Paradigms

Aspect	D&C	DP	Greedy
Subproblems	Independent	Overlapping	One choice
Combine	Merge results	Use cached	None
Order	Top-down	Usually bottom-up	One pass
Example	Merge sort	Fibonacci	Activity selection

Practice Problems

Beginner (800-1100)

Problem	Concept	Link
Merge Sort	Basic D&C	Classic
Maximum Subarray	D&C approach	LeetCode 53

Intermediate (1100-1400)

Problem	Concept	Link
Count Inversions	Merge sort variant	CSES
Kth Largest	Quick select	LeetCode 215

Advanced (1400-1700)

Problem	Concept	Link
Closest Pair	Geometric D&C	CSES
Towers	D&C + data structure	CF 37D

Key Takeaways

Split in Half

Most D&C algorithms split the problem into two equal halves.

O(n log n)

The magic of D&C: reduce O(n²) to O(n log n).

Combine Efficiently

The combine step must be O(n) or better for efficiency.

Master Theorem

Use it to analyze D&C recurrences quickly.

Next Up

Chapter 11: Dynamic Programming Fundamentals

Enter the world of DP—the most powerful technique in competitive programming.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Divide & Conquer

Divide & Conquer

The Mental Model

The D&C Template

Pattern 1: Merge Sort

Pattern 2: Count Inversions

Pattern 3: Maximum Subarray (Kadane Alternative)

Pattern 4: Closest Pair of Points

Pattern 5: Quick Select (Kth Smallest)

The Master Theorem

Common Mistakes

D&C vs Other Paradigms

Practice Problems

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1700)

Key Takeaways

Split in Half

O(n log n)

Combine Efficiently

Master Theorem

Next Up

Chapter 11: Dynamic Programming Fundamentals

​Divide & Conquer

​The Mental Model

​The D&C Template

​Pattern 1: Merge Sort

​Pattern 2: Count Inversions

​Pattern 3: Maximum Subarray (Kadane Alternative)

​Pattern 4: Closest Pair of Points

​Pattern 5: Quick Select (Kth Smallest)

​The Master Theorem

​Common Mistakes

​D&C vs Other Paradigms

​Practice Problems

​Beginner (800-1100)

​Intermediate (1100-1400)

​Advanced (1400-1700)

​Key Takeaways

Split in Half

O(n log n)

Combine Efficiently

Master Theorem

​Next Up

Chapter 11: Dynamic Programming Fundamentals

Divide & Conquer

The Mental Model

The D&C Template

Pattern 1: Merge Sort

Pattern 2: Count Inversions

Pattern 3: Maximum Subarray (Kadane Alternative)

Pattern 4: Closest Pair of Points

Pattern 5: Quick Select (Kth Smallest)

The Master Theorem

Common Mistakes

D&C vs Other Paradigms

Practice Problems

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1700)

Key Takeaways

Next Up