Problem 38.7 · Advanced Search and Divide & ConquerHard

Closest Pair of Points

What it teaches: Geometric divide and conquer with the strip argument.

In plain words

You have dots on a map and want the two that are closest. Sort them left to right, cut the map down the middle, and find the closest pair on each side. The only pairs you might have missed cross the cut, and they must sit in a thin strip near the cut line, so you only check a few neighbours there.

Return the smallest squared distance. Example: points = [[0,0],[3,4],[1,1],[10,10]] → 2.

The problem

Given at least two points, return the smallest squared Euclidean distance between any two of them.

Example 1

Input: points = [[0,0],[3,4],[1,1],[10,10]]
Output: 2

Constraints

2 ≤ n ≤ 10⁵
|coordinates| ≤ 10⁴

Pattern clues in the wording

→ Nearest two points among many

These clues point to Divide and Conquer: Split the input into halves, solve each half recursively, and combine the results.

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public long closestPair(int[][] points) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	points = [[0,0],[3,4],[1,1],[10,10]]	2
2	points = [[0,0],[5,5]]	50
3	points = [[1,2],[1,2],[3,3]]	0

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Brute force · O(n²)2. Divide and conquer · O(n log n)

Brute force

Time O(n²) Space O(1)

Compare every pair.

Approach 1

class Solution {
    public long closestPair(int[][] points) {
        long best = Long.MAX_VALUE;
        for (int i = 0; i < points.length; i++)
            for (int j = i + 1; j < points.length; j++) {
                long dx = points[i][0] - points[j][0], dy = points[i][1] - points[j][1];
                best = Math.min(best, dx * dx + dy * dy);
            }
        return best;
    }
}

Verdict: Fine for a few thousand points.

Divide and conquer

Time O(n log n) Space O(n)

Sort by x; solve(lo, hi) returns the best squared distance and merges the range by y (like merge sort); the strip check compares points within sqrt(best) of the middle x.

▶ Dry run: Split, solve each half, check the strippoints = [[0,0],[3,4],[1,1],[10,10]]

(0,0)

(1,1)

(3,4)

↑mid

(10,10)

Step 1/5Sort by x. Cut at index 2 (x = 3): left half (0,0), (1,1); right half (3,4), (10,10).

Approach 2

import java.util.*;

class Solution {
    private int[][] p;
    private int[][] buf;

    public long closestPair(int[][] points) {
        p = points.clone();
        Arrays.sort(p, Comparator.comparingInt(a -> a[0]));
        buf = new int[p.length][];
        return solve(0, p.length);
    }

    private long solve(int lo, int hi) {                 // [lo, hi); leaves p[lo..hi) sorted by y
        if (hi - lo <= 1) return Long.MAX_VALUE;
        int mid = (lo + hi) >>> 1;
        int midX = p[mid][0];
        long best = Math.min(solve(lo, mid), solve(mid, hi));
        // merge by y
        int i = lo, j = mid, k = lo;
        while (i < mid || j < hi) buf[k++] = (j >= hi || (i < mid && p[i][1] <= p[j][1])) ? p[i++] : p[j++];
        System.arraycopy(buf, lo, p, lo, hi - lo);
        // strip check
        List<int[]> strip = new ArrayList<>();
        for (int t = lo; t < hi; t++) {
            long dx = p[t][0] - midX;
            if (dx * dx < best) {
                for (int s = strip.size() - 1; s >= 0; s--) {
                    long dy = p[t][1] - strip.get(s)[1];
                    if (dy * dy >= best) break;
                    long ddx = p[t][0] - strip.get(s)[0];
                    best = Math.min(best, ddx * ddx + dy * dy);
                }
                strip.add(p[t]);
            }
        }
        return best;
    }
}

Verdict: The classic geometric algorithm.

Before you submit

Edge cases and common mistakes

Test these inputs

Duplicate points (0)
All points on a vertical line

Mistakes people make

Taking square roots and comparing doubles (keep squared integers).

Interview

Follow-up questions

Is there a simpler expected-O(n) method?

Connect the dots

Where this shows up in real systems

System Design · System 12.34 — Proximity Service (Nearby Places / Yelp)Nearby search splits space into cells (geohash, quadtrees): divide and conquer on coordinates.

Command Palette