Divide & Conquer

Chapter 22 · Part 4: ALGORITHMS · Est. 21 min read

Chapter Goal: Master Divide & Conquer — the paradigm that powers merge sort, quickselect, fast exponentiation, and the closest pair of points algorithm. D&C decomposes a problem into independent subproblems, conquers each recursively, then combines their results. Unlike DP (overlapping subproblems), D&C subproblems are disjoint, which enables the clean recursion trees that make analysis via the Master Theorem straightforward.

22.1 The D&C Paradigm — Divide, Conquer, Combine

The Three Steps

DIVIDE:   Split the problem into smaller subproblems (usually 2 halves)
CONQUER:  Solve each subproblem recursively (base case: trivially small)
COMBINE:  Merge the subproblem solutions into the answer for the whole problem

The Universal Template

T solve(Problem P) {
    // BASE CASE: problem small enough to solve directly
    if (P.size() <= THRESHOLD) return directSolve(P);
 
    // DIVIDE: split into subproblems
    auto [left, right] = divide(P);
 
    // CONQUER: solve each recursively
    T leftResult  = solve(left);
    T rightResult = solve(right);
 
    // COMBINE: merge the results
    return combine(leftResult, rightResult, P);
}

Recursion Tree — Visualizing D&C

Merge Sort on n elements:

                     [n elements]           ← O(n) combine work
                    /             \
           [n/2 elements]    [n/2 elements] ← O(n/2) + O(n/2) = O(n)
           /         \       /         \
       [n/4]       [n/4]  [n/4]      [n/4]  ← O(n) total
        ...           ...
      [1][1][1]...[1]                        ← n leaves, O(1) each

Total levels:  log₂n
Work per level: O(n)
Total time:    O(n log n)

22.2 D&C vs. DP — The Key Distinction

DIVIDE & CONQUER:
  Subproblems are INDEPENDENT (non-overlapping)
  Each subproblem is solved once → no memoization needed
  Example: merge sort — left half and right half don't share elements

DYNAMIC PROGRAMMING:
  Subproblems OVERLAP — same subproblem solved multiple times
  Memoization avoids redundant computation
  Example: Fibonacci — fib(4) needs fib(3) AND fib(2),
           fib(3) also needs fib(2) → overlap!

Property	D&C	DP
Subproblem independence	Independent	Overlapping
Memoization needed	No	Yes
Typical complexity	O(n log n)	O(n²) or O(n×k)
Examples	Merge sort, Quickselect	LCS, Knapsack, Fibonacci

How to tell them apart:
  Draw the recursion tree.
  Do any two nodes call the SAME subproblem?
  YES → overlapping → DP opportunity
  NO  → independent → D&C

22.3 Master Theorem — Analyzing D&C Complexity

The Recurrence Form

Any D&C algorithm that:

Divides a problem of size n into a subproblems
Each of size n/b
Does f(n) work to divide and combine

has time complexity satisfying: T(n) = a·T(n/b) + f(n)

Three Cases

Let the critical exponent be c* = log_b(a).

Case 1 — Work dominated by leaves:
  If f(n) = O(n^(c*−ε)) for some ε > 0  (f grows slower than n^c*)
  Then T(n) = Θ(n^c*)

Case 2 — Work balanced across all levels:
  If f(n) = Θ(n^c* × log^k(n)) for k ≥ 0
  Then T(n) = Θ(n^c* × log^(k+1)(n))
  Special case (k=0): f(n) = Θ(n^c*) → T(n) = Θ(n^c* × log n)

Case 3 — Work dominated by root:
  If f(n) = Ω(n^(c*+ε)) for some ε > 0, AND af(n/b) ≤ cf(n) for c < 1 (regularity)
  Then T(n) = Θ(f(n))

Master Theorem Reference Table

Algorithm	a	b	f(n)	c*=log_b(a)	Case	T(n)
Merge Sort	2	2	O(n)	1	2	O(n log n)
Binary Search	1	2	O(1)	0	2	O(log n)
Quickselect (avg)	1	2	O(n)	0	3	O(n)
Standard Matrix Mult	8	2	O(n²)	3	2	O(n³)
Strassen Matrix Mult	7	2	O(n²)	2.807	1	O(n^2.807)
Closest Pair of Points	2	2	O(n log n)	1	2	O(n log² n) → O(n log n) with optimization
Karatsuba Mult	3	2	O(n)	1.585	1	O(n^1.585)
Fast Power (Pow)	1	2	O(1)	0	2	O(log n)

Applying the Master Theorem — Step by Step

Merge Sort: T(n) = 2T(n/2) + O(n)
  a=2, b=2, f(n)=n
  c* = log₂(2) = 1
  f(n) = n = n^1 = n^c* → Case 2 (k=0)
  T(n) = Θ(n^1 × log n) = Θ(n log n) ✓

Binary Search: T(n) = T(n/2) + O(1)
  a=1, b=2, f(n)=1
  c* = log₂(1) = 0
  f(n) = 1 = n^0 = n^c* → Case 2 (k=0)
  T(n) = Θ(n^0 × log n) = Θ(log n) ✓

Strassen: T(n) = 7T(n/2) + O(n²)
  a=7, b=2, f(n)=n²
  c* = log₂(7) ≈ 2.807
  f(n) = n² = O(n^(2.807-0.807)) → Case 1
  T(n) = Θ(n^2.807) ✓

22.4 Merge Sort Template (Revisited)

Merge Sort is the canonical D&C algorithm. It appears directly in the "Count Inversions" problem and powers several other D&C counting problems.

void merge(vector<int>& arr, int l, int mid, int r) {
    vector<int> left(arr.begin()+l,   arr.begin()+mid+1);
    vector<int> right(arr.begin()+mid+1, arr.begin()+r+1);
    int i=0, j=0, k=l;
    while (i<(int)left.size() && j<(int)right.size())
        arr[k++] = (left[i]<=right[j]) ? left[i++] : right[j++];
    while (i<(int)left.size())  arr[k++]=left[i++];
    while (j<(int)right.size()) arr[k++]=right[j++];
}
 
void mergeSort(vector<int>& arr, int l, int r) {
    if (l>=r) return;
    int mid=l+(r-l)/2;
    mergeSort(arr,l,mid);
    mergeSort(arr,mid+1,r);
    merge(arr,l,mid,r);
}
// T(n) = 2T(n/2) + O(n) → O(n log n) by Master Theorem Case 2
// Stable sort: the <= in merge preserves original order of equal elements

22.5 Quickselect — Kth Element in O(n) Average

Quickselect finds the k-th smallest element without fully sorting the array. It uses the same partition logic as Quicksort but only recurses on one side.

Standard Quickselect

// Lomuto partition: returns final position of pivot
int partition(vector<int>& nums, int lo, int hi) {
    int pivot = nums[hi], i = lo-1;
    for (int j=lo; j<hi; j++)
        if (nums[j]<=pivot) swap(nums[++i], nums[j]);
    swap(nums[i+1], nums[hi]);
    return i+1;
}
 
// Find k-th smallest (0-indexed k)
int quickselect(vector<int>& nums, int lo, int hi, int k) {
    if (lo==hi) return nums[lo];
    int pivotIdx = partition(nums, lo, hi);
 
    if (pivotIdx==k)      return nums[pivotIdx];  // Found it
    else if (pivotIdx>k)  return quickselect(nums, lo, pivotIdx-1, k);
    else                  return quickselect(nums, pivotIdx+1, hi, k);
}
 
// Kth Largest Element (LC 215): k-th largest = (n-k)-th smallest
int findKthLargest(vector<int>& nums, int k) {
    int n = nums.size();
    return quickselect(nums, 0, n-1, n-k);  // n-k for 0-indexed
}
// Average: O(n) — T(n) = T(n/2) + O(n) by Master Theorem Case 3
// Worst:   O(n²) — sorted array with last-element pivot

Randomized Quickselect — Eliminating Worst Case

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int quickselectRandom(vector<int>& nums, int lo, int hi, int k) {
    if (lo==hi) return nums[lo];
 
    // Random pivot selection
    int pivotIdx = lo + rng() % (hi-lo+1);
    swap(nums[pivotIdx], nums[hi]);        // Move to end for Lomuto
    pivotIdx = partition(nums, lo, hi);
 
    if (pivotIdx==k)     return nums[pivotIdx];
    else if (pivotIdx>k) return quickselectRandom(nums, lo, pivotIdx-1, k);
    else                 return quickselectRandom(nums, pivotIdx+1, hi, k);
}
// Expected O(n), worst case O(n²) with probability 1/n! (negligible)

Quickselect vs. Heap for Top-K

Approach	Time	Space	Modifies Array	Returns
Sort	O(n log n)	O(log n)	Yes	K-th element + sorted
Min-heap of size k	O(n log k)	O(k)	No	K largest elements
Quickselect	O(n) avg	O(log n)	Yes	K-th element only
`nth_element` (STL)	O(n) avg	O(log n)	Yes	K-th + partitioned

// STL nth_element: O(n) average, partitions around kth element
nth_element(nums.begin(), nums.begin()+k, nums.end());
// nums[k] = k-th smallest; nums[0..k-1] ≤ nums[k] ≤ nums[k+1..]
// (not fully sorted, just partitioned)
 
// For k-th largest:
nth_element(nums.begin(), nums.begin()+(n-k), nums.end());
return nums[n-k];

22.6 Count Inversions — Modified Merge Sort

An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. The key insight: during the merge step of merge sort, when we pick an element from the RIGHT half, all remaining elements in the LEFT half form inversions with it.

long long mergeCount(vector<int>& arr, int l, int r) {
    if (l>=r) return 0;
    int mid=l+(r-l)/2;
    long long count = mergeCount(arr,l,mid) + mergeCount(arr,mid+1,r);
 
    // Count inversions during merge
    vector<int> temp;
    int i=l, j=mid+1;
    while (i<=mid && j<=r) {
        if (arr[i]<=arr[j]) {
            temp.push_back(arr[i++]);
        } else {
            // arr[i..mid] are all > arr[j] (left half is sorted)
            // Each of them forms an inversion with arr[j]
            count += (mid-i+1);
            temp.push_back(arr[j++]);
        }
    }
    while (i<=mid) temp.push_back(arr[i++]);
    while (j<=r)   temp.push_back(arr[j++]);
    copy(temp.begin(), temp.end(), arr.begin()+l);
    return count;
}
 
long long countInversions(vector<int>& arr) {
    return mergeCount(arr, 0, arr.size()-1);
}
// Time: O(n log n), Space: O(n)
 
/*
  arr = [2, 4, 1, 3, 5]
  Inversions: (2,1), (4,1), (4,3) → 3 inversions
 
  Merge sort trace:
  Split → [2,4,1] and [3,5]
  Split → [2,4] and [1], [3] and [5]
  Merge [2,4] and [1]: pick 1, count += 2 (both 2 and 4 > 1)
  Merge [2,4,1]→[1,2,4] and [3,5]→[3,5]:
    pick 1 (no inversions), pick 2 (no inv), pick 3 (no inv), pick 4 (no inv), pick 5
    → 0 inversions from this merge
  Wait, let me redo: from [1,2,4] merge with [3,5]:
    1 ≤ 3: pick 1
    2 ≤ 3: pick 2
    4 > 3: pick 3, count += 1 (only 4 remains in left)
    4 ≤ 5: pick 4
    pick 5
  Total: 2 + 0 + 1 = 3 ✓
*/

22.7 Closest Pair of Points — O(n log n)

The Problem

Given n points in 2D space, find the pair with minimum Euclidean distance. Brute force: O(n²). D&C achieves O(n log n).

The Algorithm

1. Sort points by x-coordinate: O(n log n) preprocessing
2. DIVIDE: split at median x into left and right halves
3. CONQUER: find closest pair in each half → d_left, d_right
4. COMBINE: let d = min(d_left, d_right)
            Check pairs crossing the midline within a "strip" of width 2d
5. Return min(d, d_strip)

The Strip — Why Only O(n) Pairs to Check

Key insight: In the strip of width 2d, within a window of height d on each side,
at most 8 points can fit (since each half has no pair closer than d).
Therefore each point needs to check at most 7 others in the strip.

Proof sketch:
  In a rectangle of width 2d × height 2d, divide into 8 sub-rectangles (2×4 grid).
  Each sub-rectangle has dimensions d/2 × d, with diameter = sqrt((d/2)²+d²) < d.
  Each sub-rectangle can contain at most 1 point (otherwise two points in same
  half would be closer than d, contradicting our conquer step).
  → At most 8 points in any 2d × 2d window → at most 7 comparisons per point.

Implementation

#include <cmath>
struct Point { double x, y; };
 
double dist(Point& a, Point& b) {
    return hypot(a.x-b.x, a.y-b.y);
}
 
double stripClosest(vector<Point>& strip, double d) {
    // Strip is sorted by y. Check points within vertical distance d.
    double minDist = d;
    sort(strip.begin(), strip.end(), [](auto& a, auto& b){ return a.y < b.y; });
 
    for (int i=0; i<(int)strip.size(); i++) {
        for (int j=i+1; j<(int)strip.size() && strip[j].y-strip[i].y<d; j++) {
            minDist = min(minDist, dist(strip[i], strip[j]));
        }
    }
    return minDist;
}
 
double closestRec(vector<Point>& pts, int l, int r) {
    if (r-l <= 3) {    // Base case: brute force small arrays
        double d = DBL_MAX;
        for (int i=l; i<=r; i++)
            for (int j=i+1; j<=r; j++)
                d = min(d, dist(pts[i], pts[j]));
        sort(pts.begin()+l, pts.begin()+r+1, [](auto& a, auto& b){ return a.y < b.y; });
        return d;
    }
 
    int mid = l+(r-l)/2;
    double midX = pts[mid].x;
    double d = min(closestRec(pts,l,mid), closestRec(pts,mid+1,r));
 
    // Merge by y (required for strip check at each level)
    inplace_merge(pts.begin()+l, pts.begin()+mid+1, pts.begin()+r+1,
                  [](auto& a, auto& b){ return a.y < b.y; });
 
    // Build strip: points within d of the midline
    vector<Point> strip;
    for (int i=l; i<=r; i++)
        if (abs(pts[i].x - midX) < d) strip.push_back(pts[i]);
 
    return min(d, stripClosest(strip, d));
}
 
double closestPair(vector<Point>& pts) {
    sort(pts.begin(), pts.end(), [](auto& a, auto& b){ return a.x < b.x; });
    return closestRec(pts, 0, pts.size()-1);
}
// Time: O(n log² n) with the above, O(n log n) with pre-sorted y-copy
// Space: O(n log n) for merge buffers

22.8 D&C on Expressions & Structures

Fast Exponentiation — Pow(x, n) (LC 50)

// D&C: pow(x,n) = pow(x,n/2)² if n even
//               = x × pow(x,n/2)² if n odd
double myPow(double x, long long n) {
    if (n == 0) return 1.0;
    if (n < 0) { x = 1/x; n = -n; }
 
    double half = myPow(x, n/2);
    if (n % 2 == 0) return half * half;
    else            return half * half * x;
}
// T(n) = T(n/2) + O(1) → O(log n) by Master Theorem Case 2

Different Ways to Add Parentheses (LC 241)

Compute all possible results of adding parentheses to an expression. D&C: for each operator, split the expression and recurse on both sides.

vector<int> diffWaysToCompute(string expr) {
    vector<int> results;
 
    for (int i=0; i<(int)expr.size(); i++) {
        char c = expr[i];
        if (c=='+' || c=='-' || c=='*') {
            // DIVIDE at operator i
            auto left  = diffWaysToCompute(expr.substr(0, i));
            auto right = diffWaysToCompute(expr.substr(i+1));
 
            // COMBINE: combine every left result with every right result
            for (int l : left) {
                for (int r : right) {
                    if      (c=='+') results.push_back(l+r);
                    else if (c=='-') results.push_back(l-r);
                    else             results.push_back(l*r);
                }
            }
        }
    }
 
    // Base case: no operator found → pure number
    if (results.empty()) results.push_back(stoi(expr));
    return results;
}
// Time: O(n × Catalan(n)) — Catalan number Cn = C(2n,n)/(n+1)
// Add memoization (map<string,vector<int>>) to avoid recomputing same subexpressions

The Skyline Problem (LC 218) — D&C Merge

// Represent skyline as {x, h} events, merge two skylines
using Skyline = vector<pair<int,int>>;
 
Skyline merge(Skyline& L, Skyline& R) {
    Skyline result;
    int h1=0, h2=0, i=0, j=0;
 
    while (i<(int)L.size() && j<(int)R.size()) {
        int x, h;
        if (L[i].first < R[j].first) {
            x=L[i].first; h1=L[i].second; i++;
        } else if (L[i].first > R[j].first) {
            x=R[j].first; h2=R[j].second; j++;
        } else {
            x=L[i].first; h1=L[i].second; h2=R[j].second; i++; j++;
        }
        int maxH = max(h1, h2);
        if (result.empty() || result.back().second != maxH)
            result.push_back({x, maxH});
    }
    while (i<(int)L.size()) {
        if (result.back().second!=L[i].second) result.push_back(L[i]);
        i++;
    }
    while (j<(int)R.size()) {
        if (result.back().second!=R[j].second) result.push_back(R[j]);
        j++;
    }
    return result;
}
 
// D&C divide and merge skylines
Skyline getSkyline_DC(vector<vector<int>>& buildings, int l, int r) {
    if (l==r) {
        return {{buildings[l][0], buildings[l][2]},
                {buildings[l][1], 0}};
    }
    int mid=l+(r-l)/2;
    auto L = getSkyline_DC(buildings, l, mid);
    auto R = getSkyline_DC(buildings, mid+1, r);
    return merge(L, R);
}
// Time: T(n) = 2T(n/2) + O(n) → O(n log n)

22.9 Sample Problems

Problem 1 — Kth Largest Element in an Array (Medium) — LC 215

int findKthLargest(vector<int>& nums, int k) {
    mt19937 rng(42);
    int n=nums.size(), target=n-k;
 
    function<int(int,int)> qs=[&](int lo,int hi)->int{
        int pivIdx=lo+rng()%(hi-lo+1);
        swap(nums[pivIdx],nums[hi]);
        int i=lo-1;
        for(int j=lo;j<hi;j++) if(nums[j]<=nums[hi]) swap(nums[++i],nums[j]);
        swap(nums[i+1],nums[hi]);
        int p=i+1;
        if(p==target) return nums[p];
        return p>target?qs(lo,p-1):qs(p+1,hi);
    };
    return qs(0,n-1);
}
// Time: O(n) average, Space: O(log n) recursion

Problem 2 — Sort an Array (Medium) — LC 912

void mergeSort(vector<int>& nums, int l, int r) {
    if(l>=r) return;
    int mid=l+(r-l)/2;
    mergeSort(nums,l,mid); mergeSort(nums,mid+1,r);
    vector<int> tmp;
    int i=l,j=mid+1;
    while(i<=mid&&j<=r) tmp.push_back(nums[i]<=nums[j]?nums[i++]:nums[j++]);
    while(i<=mid)  tmp.push_back(nums[i++]);
    while(j<=r)    tmp.push_back(nums[j++]);
    copy(tmp.begin(),tmp.end(),nums.begin()+l);
}
vector<int> sortArray(vector<int>& nums){mergeSort(nums,0,nums.size()-1);return nums;}
// Time: O(n log n), Space: O(n)

Problem 3 — Maximum Subarray (Medium) — LC 53 (D&C Approach)

// D&C: max subarray is entirely in left, entirely in right, or crosses midpoint
int maxSubarrayDC(vector<int>& nums, int l, int r) {
    if(l==r) return nums[l];
    int mid=l+(r-l)/2;
    int leftMax  = maxSubarrayDC(nums,l,mid);
    int rightMax = maxSubarrayDC(nums,mid+1,r);
 
    // Max crossing subarray: extend as far left and right from mid
    int leftCross=INT_MIN, sum=0;
    for(int i=mid;i>=l;i--){sum+=nums[i];leftCross=max(leftCross,sum);}
    int rightCross=INT_MIN; sum=0;
    for(int i=mid+1;i<=r;i++){sum+=nums[i];rightCross=max(rightCross,sum);}
 
    return max({leftMax, rightMax, leftCross+rightCross});
}
int maxSubArray(vector<int>& nums){return maxSubarrayDC(nums,0,nums.size()-1);}
// Time: O(n log n) — T(n)=2T(n/2)+O(n)
// Note: Kadane's O(n) is simpler; this shows D&C thinking

Problem 4 — Pow(x, n) (Medium) — LC 50

double myPow(double x, long long n) {
    if(n==0) return 1.0;
    if(n<0){x=1.0/x;n=-n;}
    double half=myPow(x,n/2);
    return n%2==0 ? half*half : half*half*x;
}
// Time: O(log n), Space: O(log n) recursion stack

Problem 5 — Count Inversions (Classic)

long long countInversions(vector<int>& arr) {
    function<long long(int,int)> dc=[&](int l,int r)->long long{
        if(l>=r) return 0;
        int mid=l+(r-l)/2;
        long long cnt=dc(l,mid)+dc(mid+1,r);
        vector<int> tmp; int i=l,j=mid+1;
        while(i<=mid&&j<=r){
            if(arr[i]<=arr[j]) tmp.push_back(arr[i++]);
            else{cnt+=(mid-i+1);tmp.push_back(arr[j++]);}
        }
        while(i<=mid) tmp.push_back(arr[i++]);
        while(j<=r)   tmp.push_back(arr[j++]);
        copy(tmp.begin(),tmp.end(),arr.begin()+l);
        return cnt;
    };
    return dc(0,arr.size()-1);
}
// Time: O(n log n), Space: O(n)

Problem 6 — Different Ways to Add Parentheses (Medium) — LC 241

// With memoization
unordered_map<string,vector<int>> memo;
 
vector<int> diffWaysToCompute(string expr) {
    if(memo.count(expr)) return memo[expr];
    vector<int> res;
    for(int i=0;i<(int)expr.size();i++){
        char c=expr[i];
        if(c=='+'||c=='-'||c=='*'){
            auto L=diffWaysToCompute(expr.substr(0,i));
            auto R=diffWaysToCompute(expr.substr(i+1));
            for(int l:L) for(int r:R){
                if(c=='+') res.push_back(l+r);
                else if(c=='-') res.push_back(l-r);
                else res.push_back(l*r);
            }
        }
    }
    if(res.empty()) res.push_back(stoi(expr));
    return memo[expr]=res;
}
// Time: O(n × Cn) with memo, Space: O(n × Cn) where Cn is Catalan number

Problem 7 — Reverse Pairs (Hard) — LC 493 (Merge Sort Approach)

Count pairs (i, j) where i < j and nums[i] > 2 × nums[j].

int reversePairs(vector<int>& nums) {
    function<int(int,int)> dc=[&](int l,int r)->int{
        if(l>=r) return 0;
        int mid=l+(r-l)/2;
        int cnt=dc(l,mid)+dc(mid+1,r);
 
        // Count reverse pairs across the two halves (both sorted)
        int j=mid+1;
        for(int i=l;i<=mid;i++){
            while(j<=r && (long long)nums[i]>2LL*nums[j]) j++;
            cnt+=j-(mid+1);
        }
 
        // Merge (standard merge sort step)
        vector<int> tmp; int a=l,b=mid+1;
        while(a<=mid&&b<=r) tmp.push_back(nums[a]<=nums[b]?nums[a++]:nums[b++]);
        while(a<=mid) tmp.push_back(nums[a++]);
        while(b<=r)   tmp.push_back(nums[b++]);
        copy(tmp.begin(),tmp.end(),nums.begin()+l);
        return cnt;
    };
    return dc(0,nums.size()-1);
}
// Time: O(n log n), Space: O(n)

Problem 8 — Count of Range Sum (Hard) — LC 327

Count the number of range sums that lie in [lower, upper].

int countRangeSum(vector<int>& nums, int lower, int upper) {
    int n=nums.size();
    vector<long long> prefix(n+1,0);
    for(int i=0;i<n;i++) prefix[i+1]=prefix[i]+nums[i];
 
    // Count pairs (i,j) where lower <= prefix[j]-prefix[i] <= upper
    // = count pairs where prefix[j]-upper <= prefix[i] <= prefix[j]-lower
    function<int(int,int)> dc=[&](int l,int r)->int{
        if(l>=r) return 0;
        int mid=l+(r-l)/2;
        int cnt=dc(l,mid)+dc(mid+1,r);
 
        // Count valid pairs: left is prefix[l..mid], right is prefix[mid+1..r]
        int j1=mid+1, j2=mid+1;
        for(int i=l;i<=mid;i++){
            while(j1<=r && prefix[j1]-prefix[i]<lower)  j1++;
            while(j2<=r && prefix[j2]-prefix[i]<=upper) j2++;
            cnt+=j2-j1;
        }
 
        // Merge
        inplace_merge(prefix.begin()+l, prefix.begin()+mid+1,
                      prefix.begin()+r+1);
        return cnt;
    };
    return dc(0,n);
}
// Time: O(n log n), Space: O(n)

Problem 9 — K Closest Points to Origin (Medium) — LC 973

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    int n=points.size();
    auto dist2=[](vector<int>& p){return p[0]*p[0]+p[1]*p[1];};
 
    // Quickselect: partition until k-th closest is at index k-1
    int lo=0,hi=n-1;
    mt19937 rng(42);
    while(lo<hi){
        int pivIdx=lo+rng()%(hi-lo+1);
        swap(points[pivIdx],points[hi]);
        int i=lo-1;
        for(int j=lo;j<hi;j++)
            if(dist2(points[j])<=dist2(points[hi])) swap(points[++i],points[j]);
        swap(points[i+1],points[hi]);
        int p=i+1;
        if(p==k-1) break;
        else if(p<k-1) lo=p+1;
        else hi=p-1;
    }
    return vector<vector<int>>(points.begin(),points.begin()+k);
}
// Time: O(n) average, Space: O(log n)

Problem 10 — Find K Closest Elements (Medium) — LC 658

Given sorted array arr and target x, find the k closest elements.

vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int lo=0, hi=arr.size()-k;
 
    while(lo<hi){
        int mid=lo+(hi-lo)/2;
        // Compare arr[mid] vs arr[mid+k] as candidates for left boundary
        // If x-arr[mid] > arr[mid+k]-x, left boundary should move right
        if(x-arr[mid]>arr[mid+k]-x) lo=mid+1;
        else                          hi=mid;
    }
    return vector<int>(arr.begin()+lo, arr.begin()+lo+k);
}
// Time: O(log(n-k) + k), Space: O(1)

Problem 11 — The Skyline Problem (Hard) — LC 218

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    // Sweep line with multiset
    vector<pair<int,int>> events;
    for(auto& b:buildings){
        events.push_back({b[0],-b[2]});  // Enter: negative height
        events.push_back({b[1], b[2]});  // Exit:  positive height
    }
    sort(events.begin(),events.end());
 
    multiset<int,greater<int>> active={0};  // Heights of active buildings
    vector<vector<int>> res;
    int prevH=0;
 
    for(auto[x,h]:events){
        if(h<0) active.insert(-h);       // Building enters
        else    active.erase(active.find(h)); // Building exits
        int currH=*active.begin();
        if(currH!=prevH){
            res.push_back({x,currH});
            prevH=currH;
        }
    }
    return res;
}
// Time: O(n log n), Space: O(n)
// (Sweep line approach; D&C merge also valid — see 22.8)

Problem 12 — Beautiful Array (Medium) — LC 932

Construct an array where for every triple (i, j, k) with i < j < k, A[j] ≠ (A[i] + A[k]) / 2. (No arithmetic progression of odd+even→int)

// D&C construction: if A is beautiful, then 2A-1 (all odd) and 2A (all even)
// are both beautiful. Interleave odd on left, even on right.
vector<int> beautifulArray(int n) {
    vector<int> res = {1};
    while((int)res.size()<n){
        vector<int> tmp;
        for(int x:res) if(2*x-1<=n) tmp.push_back(2*x-1);  // Odd elements
        for(int x:res) if(2*x<=n)   tmp.push_back(2*x);     // Even elements
        res=tmp;
    }
    return res;
}
// Time: O(n log n), Space: O(n)

22.10 LeetCode Problem Set

#	Problem	Difficulty	Core Technique	Link
1	Kth Largest Element in Array	Medium	Randomized Quickselect	LC 215
2	Sort an Array	Medium	Merge Sort implementation	LC 912
3	Maximum Subarray	Medium	D&C cross-midpoint combine	LC 53
4	Pow(x, n)	Medium	Fast power via D&C halving	LC 50
5	Different Ways to Add Parentheses	Medium	D&C split at each operator	LC 241
6	Reverse Pairs	Hard	Merge sort cross-pair counting	LC 493
7	Count of Range Sum	Hard	Merge sort on prefix sums	LC 327
8	The Skyline Problem	Hard	Sweep line + multiset	LC 218

Suggested order: #1 (Kth Largest) — implement quickselect from memory. #2 (Sort Array) — clean merge sort implementation. #3 (Max Subarray) — the cross-midpoint combine is the key D&C insight. #4 (Pow) — fast power via halving. #5 (Different Ways) — D&C on expressions, add memoization. #6 (Reverse Pairs) — merge sort counting; the counting step happens BEFORE the merge. #7 (Count of Range Sum) — merge sort on prefix sums. #8 (Skyline) — the classic hard problem; sweep line is cleaner in practice.