DSA: Divide and Conquer
Solve problems by splitting into subproblems, solving recursively, and combining results.
The Divide and Conquer Paradigm
Divide and Conquer splits a problem into smaller independent subproblems, solves each recursively, then combines the results. The recurrenceT(n) = aT(n/b) + O(n^d) is analyzed with the Master Theorem.
Master Theorem (quick reference)
T(n) = aT(n/b) + O(n^d) where a = subproblems, b = size reduction factor, d = combine cost exponent.
- d > log_b(a): T(n) = O(n^d), combine dominates
- d == log_b(a): T(n) = O(n^d * log n), balanced
- d < log_b(a): T(n) = 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 → d == log_2(1) = 0 → O(log n)
Fast Power (D&C)
C++Halve the exponent each call: O(log n) multiplications instead of O(n).
Merge Sort
Split the array in half, recursively sort each half, then merge the two sorted halves. Guaranteed O(n log n) in all cases; requires O(n) extra space.
Merge Sort
Stable sort, O(n log n) worst case. Combine step (merge) does O(n) work per level; log n levels total.
- Divide: split at midpoint, recurse left and right halves
- Conquer: base case is arrays of size 1 (trivially sorted)
- Combine: two-pointer merge of sorted halves into temp array
- Space: O(n) extra for the temp merge buffer
- Preferred for linked lists and external sorting (sequential access)
Merge Sort
C++Recurse on halves, then merge with two-pointer linear scan.
Count Inversions
Count pairs (i, j) wherei < j andarr[i] > arr[j]. Piggyback on Merge Sort: during the merge step, every time a right-half element is placed before remaining left-half elements, those count as inversions.
Count Inversions via Merge Sort
When merging, if right[j] < left[i], it is inverted with all remaining left elements (m - i + 1 inversions).
- Extend merge sort: count inversions during every merge step
- When a[j] (right) < a[i] (left): inversions += (m - i + 1)
- Total inversions = 0 means already sorted; max = n*(n-1)/2 means reverse sorted
- Time: O(n log n), same as merge sort
Count Inversions
C++Merge sort variant: count cross-inversions during each merge step.
Maximum Subarray Sum (Divide and Conquer)
The maximum subarray either lies entirely in the left half, entirely in the right half, or crosses the midpoint. The crossing case is solved in O(n) by expanding outward from the midpoint.
Maximum Subarray (D&C)
At each level: max(left result, right result, crossing sum). Crossing sum scans inward from mid.
- Crossing sum: max suffix of left half + max prefix of right half
- Recurrence: T(n) = 2T(n/2) + O(n) → O(n log n)
- Kadane's algorithm solves the same problem in O(n) iteratively
- D&C version is useful when the problem also requires returning the subarray indices
Maximum Subarray (D&C)
C++Three candidates: left half, right half, crossing midpoint.
Closest Pair of Points
Find the two closest points in a 2D plane. Naive brute force is O(n²). The D&C approach achieves O(n log n) by dividing on x-coordinate and checking only a narrow strip around the dividing line.
Closest Pair of Points
Divide by x median. Recurse on each half. Check strip of width 2d around dividing line for cross-half pairs.
- Sort points by x; divide at midpoint
- d = min(closest in left half, closest in right half)
- Strip: all points with |x - mid_x| < d; sort strip by y
- For each strip point, check at most 7 neighbors (geometry guarantees this)
- Time: O(n log² n) with inner y-sort; O(n log n) if pre-sorted by y
Closest Pair of Points
C++Recurse on halves; check strip around dividing line for cross-half closest pair.
Median of Two Sorted Arrays
Find the median of two sorted arrays of sizes m and n in O(log(min(m, n))). Binary search on the smaller array to find the correct partition point.
Median of Two Sorted Arrays
Binary search partition on smaller array. Valid partition: max(left halves) <= min(right halves).
- Always binary search on the smaller array for efficiency
- Partition: cut1 elements from nums1, cut2 = (m+n+1)/2 - cut1 from nums2
- Valid if maxLeft1 <= minRight2 and maxLeft2 <= minRight1
- Even total: median = avg(max left, min right); odd: median = max left
- Time: O(log(min(m, n)))
Median of Two Sorted Arrays
C++Binary search on smaller array for the correct partition; O(log(min(m,n))).
Divide and Conquer Problem Map
All D&C algorithms share the same three-step structure; they differ in how the combine step works.
| Algorithm | Divide | Combine | Time |
|---|---|---|---|
| Merge Sort | Split at mid | Merge two sorted halves O(n) | O(n log n) |
| Quick Sort | Partition around pivot | None (in-place) | O(n log n) avg, O(n²) worst |
| Binary Search | Eliminate half | None | O(log n) |
| Count Inversions | Split at mid | Merge + count cross-inversions | O(n log n) |
| Max Subarray | Split at mid | max(left, right, crossing) | O(n log n) |
| Closest Pair | Split by x-median | Strip check around dividing line | O(n log² n) |
| Median Two Arrays | Binary search partition | Validate left/right maxima | O(log min(m,n)) |
| Fast Power | Halve exponent | Square (+ multiply if odd) | O(log n) |
Knowledge Check
1. The three steps of Divide and Conquer are:
2. Merge Sort time complexity in all cases is:
3. Quick Sort worst-case time complexity occurs when:
4. Count Inversions counts pairs (i, j) where:
5. Closest Pair of Points after the divide step checks the strip because:
6. Median of Two Sorted Arrays runs in:
7. Fast Power (x^n using D&C) computes x^n in:
8. Maximum Subarray Sum (Kadane is O(n), D&C version is):