Closest pair of points

Problem

Given n points in the plane, find smallest euclidean distance between them. The closest pair problem is a problem in computational geometry where the objective is to find a pair of points having the minimum euclidean distance between them.

Given a set of points (x, y) on a 2D cartesian plane, find the two closest points.

Examples

Example 1

1
2
3
4
5


Input: [(1, 1), (-1, -1), (3, 4), (6, 1), (-1, -6), (-4, -3)]
Output: [(-1, -1), (1, 1)]
Explanation:
The distance between (-1, -1) and (1, 1) is sqrt((1-(-1))^2 + (1-(-1))^2) = sqrt(8) ≈ 2.83.
This is the smallest distance among all pairs of points.

Example 2

1
2
3
4
5
6


Input: [(0, 0), (1, 0), (2, 0)]
Output: [(0, 0), (1, 0)] or [(1, 0), (2, 0)]
Explanation:
Both pairs have the same distance of 1.0. Either answer is acceptable.
The distance between (0,0) and (1,0) is 1.0.
The distance between (1,0) and (2,0) is 1.0.

Example 3

1
2
3
4
5


Input: [(0, 0), (3, 4)]
Output: [(0, 0), (3, 4)]
Explanation:
With only two points, they form the only possible pair.
Distance = sqrt((3-0)^2 + (4-0)^2) = sqrt(25) = 5.0.

Example 4

1
2
3
4
5


Input: [(1, 2), (3, 4), (5, 6), (7, 8)]
Output: [(1, 2), (3, 4)]
Explanation:
All consecutive pairs have distance sqrt(8) ≈ 2.83.
Any of the consecutive pairs could be returned as they all have equal minimum distance.

Example 5

1
2
3
4


Input: [(0, 0)]
Output: []
Explanation:
Single point cannot form a pair, so return empty result.

Solution

Method 1 - Brute Force Comparison

Intuition

The simplest approach is to calculate the distance between every pair of points and keep track of the minimum distance found. Since we need to check all possible pairs Cn,2) = n * (n - 1)/2, we use nested loops to compare each point with every other point, maintaining the pair with the smallest distance.

Approach

Handle edge cases: if fewer than 2 points, return empty result
Initialize minimum distance to infinity and result pair to empty
Use nested loops to check every pair of points (i, j) where i < j
For each pair, calculate Euclidean distance using the formula: sqrt((x2-x1)² + (y2-y1)²)
If current distance is smaller than minimum found so far, update minimum and result pair
Continue until all pairs are checked
Return the pair with minimum distance

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


def find_closest_pair(points):
    n = len(points)
    if n < 2:
        return []
    
    min_distance = float('inf')
    closest_pair = None
    
    for i in range(n - 1):
        for j in range(i + 1, n):
            current_distance = euclidean_distance(points[i], points[j])
            if current_distance < min_distance:
                min_distance = current_distance
                closest_pair = (points[i], points[j])
    
    return closest_pair

def euclidean_distance(p1, p2):
    return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
private:
    double distance(const vector<int>& p1, const vector<int>& p2) {
        double dx = p1[0] - p2[0];
        double dy = p1[1] - p2[1];
        return sqrt(dx * dx + dy * dy);
    }
    
public:
    vector<vector<int>> closestPair(vector<vector<int>>& points) {
        int n = points.size();
        if (n < 2) return {};
        
        double minDist = DBL_MAX;
        vector<vector<int>> ans;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double dist = distance(points[i], points[j]);
                if (dist < minDist) {
                    minDist = dist;
                    ans = {points[i], points[j]};
                }
            }
        }
        
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


import "math"

func distance(p1, p2 []int) float64 {
    dx := float64(p1[0] - p2[0])
    dy := float64(p1[1] - p2[1])
    return math.Sqrt(dx*dx + dy*dy)
}

func closestPair(points [][]int) [][]int {
    n := len(points)
    if n < 2 {
        return [][]int{}
    }
    
    minDist := math.Inf(1)
    var ans [][]int
    
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            dist := distance(points[i], points[j])
            if dist < minDist {
                minDist = dist
                ans = [][]int{points[i], points[j]}
            }
        }
    }
    
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
    private double distance(int[] p1, int[] p2) {
        double dx = p1[0] - p2[0];
        double dy = p1[1] - p2[1];
        return Math.sqrt(dx * dx + dy * dy);
    }
    
    public int[][] closestPair(int[][] points) {
        int n = points.length;
        if (n < 2) return new int[0][0];
        
        double minDist = Double.MAX_VALUE;
        int[][] ans = new int[2][2];
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double dist = distance(points[i], points[j]);
                if (dist < minDist) {
                    minDist = dist;
                    ans[0] = points[i].clone();
                    ans[1] = points[j].clone();
                }
            }
        }
        
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def distance(self, p1: List[int], p2: List[int]) -> float:
        dx = p1[0] - p2[0]
        dy = p1[1] - p2[1]
        return (dx * dx + dy * dy) ** 0.5
    
    def closest_pair(self, points: List[List[int]]) -> List[List[int]]:
        n = len(points)
        if n < 2:
            return []
        
        min_dist = float('inf')
        ans = []
        
        for i in range(n):
            for j in range(i + 1, n):
                dist = self.distance(points[i], points[j])
                if dist < min_dist:
                    min_dist = dist
                    ans = [points[i], points[j]]
        
        return ans

Complexity

⏰ Time complexity: O(N²), where N is the number of points. We check all possible pairs of points
🧺 Space complexity: O(1), only using constant extra space for variables and result

Method 2 - Divide and Conquer Approach

Intuition

We can solve this more efficiently using divide and conquer. Sort points by x-coordinate, recursively find closest pairs in left and right halves, then check if any pair across the dividing line is closer. The key insight is that we only need to check points within the minimum distance found so far from the dividing line.

Approach

Sort all points by x-coordinate
If number of points ≤ 3, use brute force
Divide points into two halves at the median x-coordinate
Recursively find closest pairs in left and right halves
Find minimum distance from the two recursive calls
Create a strip of points within minimum distance from the dividing line
Sort strip by y-coordinate and check distances between nearby points
Return the overall minimum distance pair

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71


class Solution {
private:
    double dist(const vector<int>& p1, const vector<int>& p2) {
        double dx = p1[0] - p2[0];
        double dy = p1[1] - p2[1];
        return sqrt(dx * dx + dy * dy);
    }
    
    pair<double, vector<vector<int>>> bruteForce(vector<vector<int>>& points, int left, int right) {
        double minDist = DBL_MAX;
        vector<vector<int>> ans;
        
        for (int i = left; i <= right; i++) {
            for (int j = i + 1; j <= right; j++) {
                double d = dist(points[i], points[j]);
                if (d < minDist) {
                    minDist = d;
                    ans = {points[i], points[j]};
                }
            }
        }
        
        return {minDist, ans};
    }
    
    pair<double, vector<vector<int>>> closestRec(vector<vector<int>>& points, int left, int right) {
        if (right - left <= 2) {
            return bruteForce(points, left, right);
        }
        
        int mid = left + (right - left) / 2;
        int midX = points[mid][0];
        
        auto leftResult = closestRec(points, left, mid);
        auto rightResult = closestRec(points, mid + 1, right);
        
        double minDist = min(leftResult.first, rightResult.first);
        vector<vector<int>> ans = (leftResult.first < rightResult.first) ? leftResult.second : rightResult.second;
        
        vector<vector<int>> strip;
        for (int i = left; i <= right; i++) {
            if (abs(points[i][0] - midX) < minDist) {
                strip.push_back(points[i]);
            }
        }
        
        sort(strip.begin(), strip.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        
        for (int i = 0; i < strip.size(); i++) {
            for (int j = i + 1; j < strip.size() && (strip[j][1] - strip[i][1]) < minDist; j++) {
                double d = dist(strip[i], strip[j]);
                if (d < minDist) {
                    minDist = d;
                    ans = {strip[i], strip[j]};
                }
            }
        }
        
        return {minDist, ans};
    }
    
public:
    vector<vector<int>> closestPairDC(vector<vector<int>>& points) {
        if (points.size() < 2) return {};
        
        sort(points.begin(), points.end());
        return closestRec(points, 0, points.size() - 1).second;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90


import (
    "math"
    "sort"
)

type Point []int
type Result struct {
    dist   float64
    points [][]int
}

func dist(p1, p2 []int) float64 {
    dx := float64(p1[0] - p2[0])
    dy := float64(p1[1] - p2[1])
    return math.Sqrt(dx*dx + dy*dy)
}

func bruteForce(points [][]int, left, right int) Result {
    minDist := math.Inf(1)
    var ans [][]int
    
    for i := left; i <= right; i++ {
        for j := i + 1; j <= right; j++ {
            d := dist(points[i], points[j])
            if d < minDist {
                minDist = d
                ans = [][]int{points[i], points[j]}
            }
        }
    }
    
    return Result{minDist, ans}
}

func closestRec(points [][]int, left, right int) Result {
    if right-left <= 2 {
        return bruteForce(points, left, right)
    }
    
    mid := left + (right-left)/2
    midX := points[mid][0]
    
    leftResult := closestRec(points, left, mid)
    rightResult := closestRec(points, mid+1, right)
    
    var minDist float64
    var ans [][]int
    if leftResult.dist < rightResult.dist {
        minDist = leftResult.dist
        ans = leftResult.points
    } else {
        minDist = rightResult.dist
        ans = rightResult.points
    }
    
    var strip [][]int
    for i := left; i <= right; i++ {
        if math.Abs(float64(points[i][0]-midX)) < minDist {
            strip = append(strip, points[i])
        }
    }
    
    sort.Slice(strip, func(i, j int) bool {
        return strip[i][1] < strip[j][1]
    })
    
    for i := 0; i < len(strip); i++ {
        for j := i + 1; j < len(strip) && float64(strip[j][1]-strip[i][1]) < minDist; j++ {
            d := dist(strip[i], strip[j])
            if d < minDist {
                minDist = d
                ans = [][]int{strip[i], strip[j]}
            }
        }
    }
    
    return Result{minDist, ans}
}

func closestPairDC(points [][]int) [][]int {
    if len(points) < 2 {
        return [][]int{}
    }
    
    sort.Slice(points, func(i, j int) bool {
        return points[i][0] < points[j][0]
    })
    
    return closestRec(points, 0, len(points)-1).points
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78


class Solution {
    private double dist(int[] p1, int[] p2) {
        double dx = p1[0] - p2[0];
        double dy = p1[1] - p2[1];
        return Math.sqrt(dx * dx + dy * dy);
    }
    
    private Result bruteForce(int[][] points, int left, int right) {
        double minDist = Double.MAX_VALUE;
        int[][] ans = new int[2][2];
        
        for (int i = left; i <= right; i++) {
            for (int j = i + 1; j <= right; j++) {
                double d = dist(points[i], points[j]);
                if (d < minDist) {
                    minDist = d;
                    ans[0] = points[i].clone();
                    ans[1] = points[j].clone();
                }
            }
        }
        
        return new Result(minDist, ans);
    }
    
    private Result closestRec(int[][] points, int left, int right) {
        if (right - left <= 2) {
            return bruteForce(points, left, right);
        }
        
        int mid = left + (right - left) / 2;
        int midX = points[mid][0];
        
        Result leftResult = closestRec(points, left, mid);
        Result rightResult = closestRec(points, mid + 1, right);
        
        double minDist = Math.min(leftResult.dist, rightResult.dist);
        int[][] ans = (leftResult.dist < rightResult.dist) ? leftResult.points : rightResult.points;
        
        List<int[]> strip = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            if (Math.abs(points[i][0] - midX) < minDist) {
                strip.add(points[i]);
            }
        }
        
        strip.sort((a, b) -> Integer.compare(a[1], b[1]));
        
        for (int i = 0; i < strip.size(); i++) {
            for (int j = i + 1; j < strip.size() && (strip.get(j)[1] - strip.get(i)[1]) < minDist; j++) {
                double d = dist(strip.get(i), strip.get(j));
                if (d < minDist) {
                    minDist = d;
                    ans = new int[][]{strip.get(i).clone(), strip.get(j).clone()};
                }
            }
        }
        
        return new Result(minDist, ans);
    }
    
    public int[][] closestPairDC(int[][] points) {
        if (points.length < 2) return new int[0][0];
        
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        return closestRec(points, 0, points.length - 1).points;
    }
    
    private static class Result {
        double dist;
        int[][] points;
        
        Result(double dist, int[][] points) {
            this.dist = dist;
            this.points = points;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


class Solution:
    def dist(self, p1: List[int], p2: List[int]) -> float:
        dx = p1[0] - p2[0]
        dy = p1[1] - p2[1]
        return (dx * dx + dy * dy) ** 0.5
    
    def brute_force(self, points: List[List[int]], left: int, right: int) -> Tuple[float, List[List[int]]]:
        min_dist = float('inf')
        ans = []
        
        for i in range(left, right + 1):
            for j in range(i + 1, right + 1):
                d = self.dist(points[i], points[j])
                if d < min_dist:
                    min_dist = d
                    ans = [points[i], points[j]]
        
        return min_dist, ans
    
    def closest_rec(self, points: List[List[int]], left: int, right: int) -> Tuple[float, List[List[int]]]:
        if right - left <= 2:
            return self.brute_force(points, left, right)
        
        mid = left + (right - left) // 2
        mid_x = points[mid][0]
        
        left_result = self.closest_rec(points, left, mid)
        right_result = self.closest_rec(points, mid + 1, right)
        
        if left_result[0] < right_result[0]:
            min_dist, ans = left_result
        else:
            min_dist, ans = right_result
        
        strip = []
        for i in range(left, right + 1):
            if abs(points[i][0] - mid_x) < min_dist:
                strip.append(points[i])
        
        strip.sort(key=lambda p: p[1])
        
        for i in range(len(strip)):
            j = i + 1
            while j < len(strip) and (strip[j][1] - strip[i][1]) < min_dist:
                d = self.dist(strip[i], strip[j])
                if d < min_dist:
                    min_dist = d
                    ans = [strip[i], strip[j]]
                j += 1
        
        return min_dist, ans
    
    def closest_pair_dc(self, points: List[List[int]]) -> List[List[int]]:
        if len(points) < 2:
            return []
        
        points.sort(key=lambda p: p[0])
        return self.closest_rec(points, 0, len(points) - 1)[1]

Complexity

⏰ Time complexity: O(N log²N), where N is the number of points. Sorting takes O(N log N), and each recursive level takes O(N log N) for the strip processing
🧺 Space complexity: O(N), for the recursion stack and temporary arrays used in strip processing

Method 3 - Distance-Squared Optimization

Intuition

Since we only need to compare distances (not calculate actual values), we can avoid expensive square root operations by comparing squared distances instead. This optimization maintains the same algorithmic complexity but provides better constant factors and avoids floating-point precision issues.

Approach

Use the same brute force approach as Method 1
Replace distance calculation with squared distance: (x2-x1)² + (y2-y1)²
Compare squared distances instead of actual distances
This avoids sqrt() computation while maintaining correct ordering
Convert back to actual points for the final result
Handle edge cases the same way as Method 1

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
private:
    long long distanceSquared(const vector<int>& p1, const vector<int>& p2) {
        long long dx = p1[0] - p2[0];
        long long dy = p1[1] - p2[1];
        return dx * dx + dy * dy;
    }
    
public:
    vector<vector<int>> closestPairOptimized(vector<vector<int>>& points) {
        int n = points.size();
        if (n < 2) return {};
        
        long long minDistSq = LLONG_MAX;
        vector<vector<int>> ans;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long long distSq = distanceSquared(points[i], points[j]);
                if (distSq < minDistSq) {
                    minDistSq = distSq;
                    ans = {points[i], points[j]};
                }
            }
        }
        
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func distanceSquared(p1, p2 []int) int64 {
    dx := int64(p1[0] - p2[0])
    dy := int64(p1[1] - p2[1])
    return dx*dx + dy*dy
}

func closestPairOptimized(points [][]int) [][]int {
    n := len(points)
    if n < 2 {
        return [][]int{}
    }
    
    minDistSq := int64(math.MaxInt64)
    var ans [][]int
    
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            distSq := distanceSquared(points[i], points[j])
            if distSq < minDistSq {
                minDistSq = distSq
                ans = [][]int{points[i], points[j]}
            }
        }
    }
    
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
    private long distanceSquared(int[] p1, int[] p2) {
        long dx = p1[0] - p2[0];
        long dy = p1[1] - p2[1];
        return dx * dx + dy * dy;
    }
    
    public int[][] closestPairOptimized(int[][] points) {
        int n = points.length;
        if (n < 2) return new int[0][0];
        
        long minDistSq = Long.MAX_VALUE;
        int[][] ans = new int[2][2];
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long distSq = distanceSquared(points[i], points[j]);
                if (distSq < minDistSq) {
                    minDistSq = distSq;
                    ans[0] = points[i].clone();
                    ans[1] = points[j].clone();
                }
            }
        }
        
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def distance_squared(self, p1: List[int], p2: List[int]) -> int:
        dx = p1[0] - p2[0]
        dy = p1[1] - p2[1]
        return dx * dx + dy * dy
    
    def closest_pair_optimized(self, points: List[List[int]]) -> List[List[int]]:
        n = len(points)
        if n < 2:
            return []
        
        min_dist_sq = float('inf')
        ans = []
        
        for i in range(n):
            for j in range(i + 1, n):
                dist_sq = self.distance_squared(points[i], points[j])
                if dist_sq < min_dist_sq:
                    min_dist_sq = dist_sq
                    ans = [points[i], points[j]]
        
        return ans

Complexity

⏰ Time complexity: O(N²), where N is the number of points. Same as brute force but with faster constant factors
🧺 Space complexity: O(1), only using constant extra space for variables and result

Notes

Method 1 provides a straightforward brute force solution that’s easy to understand and implement
Method 2 offers optimal theoretical complexity using divide and conquer, suitable for large datasets
Method 3 optimizes the brute force approach by avoiding expensive square root calculations
For small to medium datasets (N < 1000), Method 3 often performs better than Method 2 due to simpler implementation
Method 2 is preferred for large datasets where O(N log²N) vs O(N²) makes a significant difference
All methods handle edge cases like fewer than 2 points or equal distances between multiple pairs
The problem is a classic example of computational geometry and appears frequently in interviews
Consider numerical precision when working with floating-point distances in real applications
For tie-breaking when multiple pairs have the same minimum distance, any valid pair can be returned

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Example 5#

Solution#

Method 1 - Brute Force Comparison#

Intuition#

Approach#

Pseudocode#

Code#

Complexity#

Method 2 - Divide and Conquer Approach#

Intuition#

Approach#

Code#

Complexity#

Method 3 - Distance-Squared Optimization#

Intuition#

Approach#

Code#

Complexity#

Notes#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Method 1 - Brute Force Comparison

Intuition

Approach

Pseudocode

Code

Complexity

Method 2 - Divide and Conquer Approach

Intuition

Approach

Code

Complexity

Method 3 - Distance-Squared Optimization

Intuition

Approach

Code

Complexity

Notes