APPLYDJINN
← AlgorithmsProgress & review ↗

Typorithm · hard

Closest Pair of Points

▷ Interactive algorithm labclosest-pair-of-pointsdivide-and-conquerstripgeometrycombine-step
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
1

Step 1 of 8 · intro card

Learn Closest Pair of Points

0%

Divide & Conquer

Sort by x, recurse on each half, take the smaller distance d, then check only points within a 2d-wide vertical strip, sorted by y.

Sort points by x once, then split at the median x and recurse on each half.

Let d be the smaller of the two halves' closest distances; any closer pair must straddle the midline within a strip of width 2d.

Sort the strip by y and compare each point only to the next few whose y-distance is below d — a constant number per point, keeping the combine step linear.

Preparing algorithm lab…
01

d = min of the two halves first.

02

Strip width is 2d around the midline.

03

Each strip point checks only a few y-neighbors.

function closestPair(points) {
  const byX = [...points].sort((a, b) => a.x - b.x);

  function dist(a, b) {
    return Math.hypot(a.x - b.x, a.y - b.y);
  }

  function solve(lo, hi) {
    if (hi - lo <= 3) {
      let best = Infinity;
      for (let i = lo; i < hi; i += 1) {
        for (let j = i + 1; j < hi; j += 1) {
          best = Math.min(best, dist(byX[i], byX[j]));
        }
      }
      return best;
    }

    const mid = Math.floor((lo + hi) / 2);
    const midX = byX[mid].x;
    let d = Math.min(solve(lo, mid), solve(mid, hi));

    const strip = [];
    for (let i = lo; i < hi; i += 1) {
      if (Math.abs(byX[i].x - midX) < d) strip.push(byX[i]);
    }
    strip.sort((a, b) => a.y - b.y);

    for (let i = 0; i < strip.length; i += 1) {
      for (let j = i + 1; j < strip.length && strip[j].y - strip[i].y < d; j += 1) {
        d = Math.min(d, dist(strip[i], strip[j]));
      }
    }

    return d;
  }

  return solve(0, byX.length);
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Sort by x

Sorting by x once lets each recursion split at the median x in order.

const byX = [...points].sort((a, b) => a.x - b.x)

2. Small base case

With three or fewer points, brute-force every pair directly.

if (hi - lo <= 3)

3. Conquer halves

Recurse into each half; d is the smaller of the two halves' best distances.

let d = Math.min(solve(lo, mid), solve(mid, hi))

4. Build the strip

Only points within distance d of the midline can beat d across halves.

if (Math.abs(byX[i].x - midX) < d) strip.push(byX[i])

5. Sort strip by y

Sorting the strip by y bounds each point to a few following neighbors.

strip.sort((a, b) => a.y - b.y)

6. Check few neighbors

Stop once the y-gap reaches d; only a constant number of points qualify.

strip[j].y - strip[i].y < d

A complete learning loop

01

Understand

Read the concept map and follow the code breakdown.

02

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

03

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.

Closest Pair of Points: Visual Walkthrough & Practice · Typorithm | ApplyDjinn