DIVIDE AND CONQUER PROBLEM-SOLVING TRICKS
Essential Divide and Conquer Techniques
| # | Technique | Description |
|---|---|---|
| 1 | Recursive decomposition | Break problems into smaller subproblems until base case is reached |
| 2 | Merge Sort approach | Divide array into halves, sort each half, then merge results |
| 3 | Quick Sort partitioning | Select pivot, partition array, then recursively sort partitions |
| 4 | Binary Search | Divide sorted array in halves to efficiently locate elements |
| 5 | Finding peak elements | Compare middle element with neighbors to determine search direction |
| 6 | Closest pair of points | Divide plane into regions and recursively find closest pairs |
| 7 | Strassen's matrix multiplication | Break matrix multiplication into smaller subproblems |
| 8 | Karatsuba multiplication | Fast multiplication algorithm for large numbers |
| 9 | Majority element finding | Divide array and count occurrences in each half |
| 10 | Maximum subarray problem | Find maximum contiguous subarray by dividing array |
| 11 | Skyline problem | Merge skylines from divided subproblems |
| 12 | Fast Fourier Transform | Divide polynomial evaluation into even/odd terms |
| 13 | Convex hull algorithms | Divide points into subsets and merge hulls |
| 14 | Counting inversions | Modify merge sort to count inversions during merge |
| 15 | Median of medians | Divide array to find approximate median for pivot selection |
Implementation Examples
Merge Sort Implementation
// Merge Sort in C
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}Binary Search
// Binary Search in C
int binarySearch(int arr[], int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x) return m;
if (arr[m] < x) l = m + 1;
else r = m - 1;
}
return -1;
}
// Recursive version
int binarySearchRec(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] > x)
return binarySearchRec(arr, l, mid - 1, x);
return binarySearchRec(arr, mid + 1, r, x);
}
return -1;
}Quick Sort
// Quick Sort in C
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}Closest Pair of Points
// Closest pair of points (simplified)
typedef struct { double x, y; } Point;
double bruteForce(Point P[], int n) {
double min = DBL_MAX;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (dist(P[i], P[j]) < min)
min = dist(P[i], P[j]);
return min;
}
double closestUtil(Point P[], int n) {
if (n <= 3) return bruteForce(P, n);
int mid = n/2;
Point midPoint = P[mid];
double dl = closestUtil(P, mid);
double dr = closestUtil(P + mid, n - mid);
double d = fmin(dl, dr);
// Check strip of points within d distance of middle line
Point strip[n];
int j = 0;
for (int i = 0; i < n; i++)
if (fabs(P[i].x - midPoint.x) < d)
strip[j++] = P[i];
return fmin(d, stripClosest(strip, j, d));
}Pro Tips for Divide and Conquer
Remember: The base case is crucial in recursive Divide and Conquer algorithms to prevent infinite recursion.
Best Practices
- Clearly define your base case(s) first
- Ensure each recursive call makes progress toward the base case
- Combine solutions efficiently in the conquer step
- Analyze time complexity using recurrence relations
Performance Considerations
- Divide and Conquer often has O(n log n) complexity
- Recursion has overhead - consider iterative versions for small n
- Memoization can optimize overlapping subproblems
- Tail recursion optimization can help with stack usage