Closest Pair of Points

Problem Statement

Given an array of n points in a 2D plane, find the pair of points with the minimum Euclidean distance between them.

Example: Input: points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
Output: Minimum distance = 1.414 (between points (2, 3) and (3, 4))
Explanation: Distance = √[(3-2)² + (4-3)²] = √2 ≈ 1.414

Approach 1: Brute Force

Explanation: Calculate the distance between every pair of points using nested loops and keep track of the minimum distance found.

Time Complexity: O(n2)

Space Complexity: O(1)

function distance(p1, p2):
    return sqrt((p1.x - p2.x)² + (p1.y - p2.y)²)

function closestPair(points):
    n = length(points)
    minDist = infinity
    
    for i = 0 to n-2:
        for j = i+1 to n-1:
            dist = distance(points[i], points[j])
            if dist < minDist:
                minDist = dist
                pair = (points[i], points[j])
    
    return minDist

Approach 2: Sort by X-coordinate then Brute Force

Explanation: Sort points by x-coordinate first. For each point, only check points within a reasonable x-distance range, reducing unnecessary comparisons in practice.

Time Complexity: O(n2) worst case, better average case

Space Complexity: O(1)

function closestPair(points):
    n = length(points)
    sort(points by x-coordinate)
    minDist = infinity
    
    for i = 0 to n-2:
        for j = i+1 to n-1:
            // Early termination if x-distance exceeds minDist
            if points[j].x - points[i].x >= minDist:
                break
            
            dist = distance(points[i], points[j])
            if dist < minDist:
                minDist = dist
                pair = (points[i], points[j])
    
    return minDist

Approach 3: Divide and Conquer

Explanation: Sort points by x-coordinate and divide into two halves. Recursively find closest pairs in both halves. The minimum distance could be in left half, right half, or across the dividing line. Check the strip near the dividing line efficiently.

Time Complexity: O(n log n) with optimization

Space Complexity: O(n)

function stripClosest(strip, d):
    minDist = d
    sort(strip by y-coordinate)
    
    for i = 0 to length(strip)-1:
        j = i + 1
        while j < length(strip) and (strip[j].y - strip[i].y) < minDist:
            minDist = min(minDist, distance(strip[i], strip[j]))
            j = j + 1
    
    return minDist

function closestPairRec(pointsX, pointsY):
    n = length(pointsX)
    
    // Base case: use brute force for small n
    if n <= 3:
        return bruteForce(pointsX)
    
    // Divide
    mid = n / 2
    midPoint = pointsX[mid]
    
    pointsYLeft = points from pointsY with x <= midPoint.x
    pointsYRight = points from pointsY with x > midPoint.x
    
    // Conquer
    leftDist = closestPairRec(pointsX[0...mid], pointsYLeft)
    rightDist = closestPairRec(pointsX[mid+1...n], pointsYRight)
    
    // Find minimum of left and right
    d = min(leftDist, rightDist)
    
    // Build strip array containing points within distance d from midline
    strip = []
    for i = 0 to n-1:
        if abs(pointsY[i].x - midPoint.x) < d:
            strip.append(pointsY[i])
    
    // Find closest points in strip
    return min(d, stripClosest(strip, d))

function closestPair(points):
    pointsX = sort(copy of points by x-coordinate)
    pointsY = sort(copy of points by y-coordinate)
    return closestPairRec(pointsX, pointsY)

The Divide and Conquer approach is the optimal solution with O(n log n) time complexity when properly optimized. It efficiently divides the problem into smaller subproblems and handles the merge step by checking only relevant points in the strip area.


Flowchart