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²) to O(n log n).

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 right half, all remaining left elements form inversions.

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++];
        } else {
            temp[k++] = arr[j++];
            inversions += (mid - i + 1);  // All remaining left elements
        }
    }
    
    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).

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.

int partition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo;
    
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    
    swap(arr[i], arr[hi]);
    return i;
}

int quickSelect(vector<int>& arr, int lo, int hi, int k) {
    if (lo == hi) return arr[lo];
    
    int pivotIndex = partition(arr, lo, hi);
    
    if (k == pivotIndex) {
        return arr[k];
    } else if (k < pivotIndex) {
        return quickSelect(arr, lo, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, hi, k);
    }
}

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

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

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

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

​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