Divide & ConquerAlgorithmaka closest pair problem, nearest pair in the plane

Closest Pair of Points

Find the two closest points among n points in the plane in O(n log n) by splitting on x, recursing, and checking only a thin strip around the split line.

Pattern: Divide and ConquerPractice (1)
Progress

Overview

Given n points, the brute force compares all n(n−1)/2 pairs in O(n²). The divide-and-conquer algorithm sorts the points by x, splits at the median vertical line, recursively finds the closest pair on each side (distance dL, dR, take d = min), and then looks for a closer pair crossing the line. The crucial observation is that any crossing pair with distance < d lies in the strip |x − x_mid| < d, and within that strip, sorted by y, each point needs to be compared with at most 7 following points.

With the points also kept sorted by y (merge the two halves' y-orders during combine, as in Merge Sort), the combine step is O(n) and the recurrence T(n) = 2T(n/2) + O(n) gives O(n log n). Sorting by y inside every call instead gives O(n log² n), which is usually acceptable in interviews.

divide and conquergeometryO(n log n)stripsorting

Intuition

A mental model before the formal terms.

Draw a vertical line through the middle of the points. The closest pair is either entirely left, entirely right, or has one point on each side. The first two cases are the recursive calls. For the third, you already know the best distance d so far — so only points within d of the line can matter; everything else is too far to cross.

Inside that strip, points cannot be packed arbitrarily: on each side of the line, every two points are at least d apart (that is what the recursion proved). So a d × 2d rectangle can hold at most 8 points. Walking the strip in y order, once a point is more than d below you, nothing further down can beat d — you only ever look at a handful of neighbors.

How it works

  1. Sort points by x once (Px) and by y once (Py).
  2. Recurse: if n ≤ 3, brute force. Otherwise split Px at the median x_mid; split Py into Ly/Ry in one pass by comparing each point's x with x_mid (preserving y-order).
  3. Let d = min(closest(L), closest(R)).
  4. Build the strip: all points of Py with |x − x_mid| < d, already in y-order.
  5. For each strip point i, compare with strip points j > i while y[j] − y[i] < d (at most 7 comparisons); update d.
  6. Return d (and the pair that achieved it).

Why it works

Any pair closer than d with points on opposite sides has both points within horizontal distance d of the line, hence in the strip; the strip scan finds it.

Packing argument: consider a d × 2d rectangle straddling the line, with the point p on its bottom edge. Each half is a d × d square whose points are pairwise ≥ d apart (they come from one side), so each half holds at most 4 points (place them at the corners; a 5th would be within d of one). Thus at most 8 points, i.e. p and 7 others; any point more than d above p in y is outside the rectangle and cannot be within d.

Since each strip point does O(1) work and splitting Py is linear, the combine step is O(n) and T(n) = 2T(n/2) + O(n) = O(n log n) by the Master theorem (case 2).

Recognition

How to tell a problem wants this.

  • "Closest / nearest two points", "minimum distance between any two of n points", with n up to 10^5..10^6 (brute force n² is too slow).
  • Points in the plane where a split by one coordinate leaves a bounded-width interaction zone.
  • Any problem phrased as "the answer is either in the left half, the right half, or crosses the middle" with a geometric pruning bound.
“merge k sorted” → Divide and Conquer

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1closest(Px, Py):
2  if |Px| <= 3: return brute force
3  mid = |Px| / 2; x_mid = Px[mid].x
4  Lx, Rx = Px[:mid], Px[mid:]
5  Ly, Ry = split Py by x < x_mid (keep y order)
6  d = min(closest(Lx, Ly), closest(Rx, Ry))
7  strip = [p in Py if |p.x - x_mid| < d]
8  for i in strip: for j = i+1 while strip[j].y - strip[i].y < d:
9    d = min(d, dist(strip[i], strip[j]))
10  return d

Implementations

1import math
2from typing import NamedTuple
3 
4# Closest pair of points in the plane in O(n log n): sort by x, split, recurse
5# on both halves, then check only a thin strip around the split line — where a
6# geometric argument bounds the work at a constant number of comparisons.
7 
8 
9class Point(NamedTuple):
10    x: float
11    y: float
12 
13 
14def dist(a: Point, b: Point) -> float:
15    return math.hypot(a.x - b.x, a.y - b.y)
16 
17 
181 · Brute force for tiny ranges; the recursion bottoms out here
19def brute_force(pts: list[Point], lo: int, hi: int) -> float:
20    best = math.inf
21    for i in range(lo, hi):
22        for j in range(i + 1, hi):
23            best = min(best, dist(pts[i], pts[j]))
24    return best
25 
26 
272 · Recurse on both halves; d is the better of the two
28def closest_rec(by_x: list[Point], lo: int, hi: int) -> float:
29    if hi - lo <= 3:
30        return brute_force(by_x, lo, hi)
31    mid = (lo + hi) // 2
32    mid_x = by_x[mid].x
33    d = min(closest_rec(by_x, lo, mid), closest_rec(by_x, mid, hi))
34 
353 · Only points within d of the split line can beat d
36    strip = [p for p in by_x[lo:hi] if abs(p.x - mid_x) < d]
37    strip.sort(key=lambda p: p.y)
38 
394 · Within the strip, sorted by y, at most 7 later points can be closer
40    # than d — because a d-by-2d rectangle holds at most 8 points that are all
41    # at least d apart from each other
42    for i, pi in enumerate(strip):
43        for j in range(i + 1, len(strip)):
44            if strip[j].y - pi.y >= d:
45                break
46            d = min(d, dist(pi, strip[j]))
47    return d
48 
49 
505 · Sort by x once, then recurse
51def closest_pair(pts: list[Point]) -> float:
52    if len(pts) < 2:
53        return math.inf
54    by_x = sorted(pts, key=lambda p: p.x)
55    return closest_rec(by_x, 0, len(by_x))
Walkthrough
  1. math.hypot(dx, dy) computes the distance without intermediate overflow, and is the idiomatic Python spelling.
  2. strip = [p for p in by_x[lo:hi] if abs(p.x - mid_x) < d] builds the strip in one comprehension, though by_x[lo:hi] copies the slice.
  3. The inner loop uses an explicit break because Python for has no compound condition — the C-style for (...; cond; ...) has no direct equivalent.
  4. for i, pi in enumerate(strip) binds the outer point once, avoiding repeated indexing in the inner loop.
  5. Point(NamedTuple) gives an immutable, tuple-backed record; note that sorted(pts) without a key would order by (x, y), which happens to be the x-order needed.
Complexity (this implementation)
time O(n log^2 n) as written · space O(n) for the strip and slice copies, O(log n) recursion depth

The by_x[lo:hi] slice at every level adds an O(n) copy per level, on top of the strip sort.

Language notes
  • math.hypot handles extreme magnitudes without overflow and accepts any number of arguments since 3.8 (so it generalises to n dimensions).
  • math.dist(p, q) (3.8+) computes the Euclidean distance between two point sequences directly, which is shorter still.
  • Python for has no compound condition, so the early exit must be an explicit break — the one place the loop reads less directly than in the other three languages.
  • scipy.spatial.KDTree.query solves the practical version of this problem and is the right tool outside a teaching context.
Common mistakes in this language
  • Slicing by_x[lo:hi] at every level and paying an extra O(n) copy per level.
  • Forgetting the break and making the strip pass quadratic.
  • Relying on sorted(pts) to sort by x — it does, but only because NamedTuple compares field by field, which is fragile if a field is ever reordered.
Language differences that matter here
  • Compound loop conditions: C++ and JS/TS put the early exit in the for header, while Python needs an explicit break — the only structural difference between the four versions.
  • Distance helpers: Python has math.hypot and math.dist, C++ has std::hypot, JS/TS have Math.hypot — all overflow-safe and all slower than the direct sqrt(dx*dx + dy*dy).
  • Immutable point records come free in Python (NamedTuple) and must be arranged in the other three; the flip side is that NamedTuple also makes sorted(pts) silently order by (x, y).
  • Every version here is O(n log^2 n) because it re-sorts the strip per level; the refinement to O(n log n) is identical in all four and is noted rather than claimed.

Complexity

Best
—
Average
—
Worst
O(n log n)
Space
O(n)

T(n) = 2T(n/2) + O(n). Re-sorting the strip by y in each call gives O(n log² n). Brute force is O(n²).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Exact closest pair for n beyond a few thousand in the Euclidean plane.
  • As a template for other "crossing-the-split" geometric problems where a distance bound limits the interaction zone.
Avoid it when
  • n ≤ ~2000 — the O(n²) brute force is simpler and fast enough.
  • Points arrive online or move — the algorithm is batch-only; use a spatial grid / k-d tree instead.
  • Non-Euclidean metrics where the packing argument fails (the 7-neighbor bound relies on the geometry of the d × 2d rectangle).

Alternatives

Divide and ConquerMerge Sort

Common mistakes

  • Building the strip from Px (x-sorted) instead of Py and then scanning without y-order — the 7-neighbor bound only holds when walking in y.
  • Using ≤ d instead of < d inconsistently, or forgetting to update d inside the strip loop (later strip points depend on the tightened bound).
  • Splitting Py by comparing x < x_mid alone when several points share x_mid — the halves no longer match Lx/Rx; split by membership or by index rank.
  • Recursing until n == 1 — an empty or singleton half yields an infinite distance, which is fine, but the base case n ≤ 3 avoids the degenerate strip.

Interview patterns

  • State the three cases (left, right, crossing) and the packing argument — that is the whole interview.
  • Follow-up: "why 7?" Draw the d × 2d rectangle with 8 corner points.
  • Follow-up: "how to get n log n instead of n log² n?" Merge the y-orders instead of sorting.
Interview questions on this
Mock interviews

Example problems

Maximum Subarraymedium