Closest Pair of Points
Sort points by x, split in half, find closest pair in each half, then check the 'strip' near the dividing line for cross-half pairs. The strip check is O(n) due to a geometric argument. Total: O(n log n).
How It Works
Closest pair of points beats the O(n^2) all-pairs check with divide and conquer. Sort points by x, split at the median into left and right halves, and recursively find the closest distance in each; let d be the smaller of the two. The only pairs still unexamined straddle the dividing line, and both members must lie within d of it — a vertical strip of width 2d.
The strip is where the magic happens: sort (or maintain) strip points by y, and compare each point only to the following points within d vertically. A packing argument shows at most a constant number of strip points (classically bounded by 7) can fit in that window, because two points in the same half are already at least d apart. So the combine step is O(n), and the recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n). Maintaining y-sorted order via merge sort avoids re-sorting each level.
Step-by-Step Visualization
Code
static double closestPair(int[][] points) {
Arrays.sort(points, (a, b) -> a[0] - b[0]);
return closestRec(points, 0, points.length - 1);
}
static double closestRec(int[][] pts, int lo, int hi) {
if (hi - lo < 3) return bruteForce(pts, lo, hi);
int mid = (lo + hi) / 2;
double dL = closestRec(pts, lo, mid);
double dR = closestRec(pts, mid + 1, hi);
double d = Math.min(dL, dR);
// Check strip of width 2d around midpoint
// ... (strip check logic)
return d;
}Tips & Gotchas
Practice Problems
- 1Closest Pair of Points
- 2K Closest Points to Origin
- 3Max Points on a Line
- 4The Skyline Problem
About the Divide & Conquer Pattern
Split the problem into two (or more) smaller subproblems, solve each independently, then combine the results. The splitting usually halves the input, giving O(n log n) algorithms.
Every recursive solution has: base case, recursive case, and combining step. For backtracking, add: make choice → recurse → undo choice. Prune early to avoid TLE.
Common Recursion Interview Problems
- Subsets
- Permutations
- Combination Sum
- N-Queens
- Word Search
- Generate Parentheses
- Letter Combinations of Phone Number
Frequently Asked Questions
Why does each strip point need comparison with only a constant number of neighbors?
Any two points on the same side of the dividing line are at least d apart by the recursive result, so a d x 2d rectangle of the strip can contain only a bounded number of points — the classic analysis bounds it at 7 or 8 candidates ahead in y-order. That constant bound is what keeps the merge step linear.
Could I skip the strip check and just take the min of the two halves?
No — the true closest pair may have one point in each half, and those cross pairs are exactly what the recursion misses. The strip confines that search to points within d of the line, checked in y-order, so correctness is restored without giving up the O(n log n) bound.
Where else does this divide-sort-and-merge pattern show up?
The same skeleton — recurse on halves, then do a linear pass to account for cross-boundary interactions — powers counting inversions with merge sort, Count of Smaller Numbers After Self, and Reverse Pairs. Recognizing the 'combine step handles pairs that straddle the split' idea is the transferable skill.