Divide and Conquer Paradigm
Divide and Conquer splits a problem into independent smaller subproblems, solves them recursively, and merges their results—powering Merge Sort, Quick Sort, Binary Search, and Closest Pair of Points.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Divide and Conquer Paradigm
Divide and Conquer solves a problem of size $n$ in three phases:
1. Divide the input into $a$ independent subproblems of size $n / b$.
2. Conquer each subproblem recursively (solving tiny base cases directly).
3. Combine the subproblem answers in $f(n)$ time.
Its runtime follows the recurrence $T(n) = a\,T(n / b) + f(n)$, solved immediately by the Master Theorem!
At a Glance
| Classic Algorithm | Recurrence | Time Complexity |
| :--- | :--- | :---: |
| Binary Search | $T(n) = T(n/2) + O(1)$ | $O(\log n)$ |
| Merge Sort | $T(n) = 2T(n/2) + O(n)$ | $O(n \log n)$ |
| Closest Pair of Points (2D) | $T(n) = 2T(n/2) + O(n)$ | $O(n \log n)$ |
| Strassen's Matrix Multiplication | $T(n) = 7T(n/2) + O(n^2)$ | $O(n^{2.807})$ |
---
Practice Problems
Intermediate
1. Closest Pair of Points in 2D ($O(n \log n)$ Divide & Conquer)
Given $n$ points in the 2D plane, find the minimum Euclidean distance between any two distinct points in $O(n \log n)$ time.
Approach: Sort by x, split at midpoint mid, recursively find d = min(dLeft, dRight), then check only points inside the vertical strip |x - midX| < d sorted by y—each point needs to check at most 7 following points in the strip! Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <vector>
struct Pt { double x, y; };
double dist(const Pt& a, const Pt& b) { return std::hypot(a.x - b.x, a.y - b.y); }
double closestRec(std::vector<Pt>& pts, int l, int r) {
if (r - l <= 3) {
double best = std::numeric_limits<double>::infinity();
for (int i = l; i <= r; ++i)
for (int j = i + 1; j <= r; ++j) best = std::min(best, dist(pts[i], pts[j]));
std::sort(pts.begin() + l, pts.begin() + r + 1, [](const Pt& a, const Pt& b) { return a.y < b.y; });
return best;
}
int mid = (l + r) / 2;
double midX = pts[mid].x;
double d = std::min(closestRec(pts, l, mid), closestRec(pts, mid + 1, r));
std::vector<Pt> merged(r - l + 1);
std::merge(pts.begin() + l, pts.begin() + mid + 1, pts.begin() + mid + 1, pts.begin() + r + 1,
merged.begin(), [](const Pt& a, const Pt& b) { return a.y < b.y; });
std::copy(merged.begin(), merged.end(), pts.begin() + l);
std::vector<Pt> strip;
for (int i = l; i <= r; ++i) if (std::abs(pts[i].x - midX) < d) strip.push_back(pts[i]);
for (size_t i = 0; i < strip.size(); ++i) {
for (size_t j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < d; ++j) {
d = std::min(d, dist(strip[i], strip[j]));
}
}
return d;
}
int main() {
std::vector<Pt> pts = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
std::sort(pts.begin(), pts.end(), [](const Pt& a, const Pt& b) { return a.x < b.x; });
std::cout << std::fixed << std::setprecision(4) << closestRec(pts, 0, static_cast<int>(pts.size()) - 1) << "\n";
return 0;
}
</details>
---
Related Algorithms
- Master Theorem — analyzes Divide-and-Conquer recurrences directly.
- Strassen's Algorithm — sub-cubic Divide-and-Conquer matrix multiplication.