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.
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;}
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;}
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.
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.
// WRONG: Infinite recursion when lo == hiif (lo > hi) return;// CORRECTif (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!)