Problem Description

Given a list of points on a 2D plane, your task is to find the shortest distance between any two distinct points. Each point is represented as an array [x, y] where x and y are integers. The Euclidean distance between two points (x1, y1) and (x2, y2) is defined as sqrt((x2 - x1)^2 + (y2 - y1)^2).

You must return the length of the shortest distance found, as a floating point number.
Constraints:

• There are at least two points (n ≥ 2).
• All points are distinct.
• You must not reuse the same point in a pair.
• There is exactly one pair of points that yields the shortest distance.

Thought Process

To solve this problem, our first instinct might be to check every possible pair of points and compute their distance, keeping track of the minimum. This brute-force approach is simple and guarantees correctness, but it can be slow for large numbers of points because the number of pairs grows quickly.

We can recall that this problem is a classic in computational geometry, often called the "closest pair of points" problem. There are advanced algorithms that can solve it faster than brute-force, such as using a divide-and-conquer strategy. However, unless the input is extremely large, the brute-force approach is often sufficient for practical purposes and much easier to implement.

In summary, the problem is about systematically comparing all pairs of points, calculating their distances, and finding the smallest one, while considering if any optimizations can be used for efficiency.

Solution Approach

Let's break down the solution step by step:

1. Iterate Over All Pairs: For every point, compare it with every other point that comes after it in the list. This ensures we don't compare the same pair twice or a point with itself.
2. Compute Distance: For each pair, calculate the Euclidean distance using the formula: sqrt((x2 - x1)^2 + (y2 - y1)^2).
3. Track the Minimum: Keep a variable to store the minimum distance found so far. If the current pair's distance is smaller, update this variable.
4. Return the Result: After all pairs have been checked, return the minimum distance found.

Why This Works: Since the number of pairs is manageable for moderate input sizes, this approach is both correct and easy to understand. If the input size was huge (e.g., tens of thousands of points), we could consider a more advanced algorithm (like divide-and-conquer in O(n log n)), but for most interview and contest settings, this is sufficient.

Example Walkthrough

Let's use the following sample input:

points = [[0, 0], [3, 4], [6, 8], [2, 1]]

1. Compare (0,0) and (3,4): Distance = sqrt((3-0)^2 + (4-0)^2) = sqrt(9+16) = sqrt(25) = 5
2. Compare (0,0) and (6,8): Distance = sqrt(36+64) = sqrt(100) = 10
3. Compare (0,0) and (2,1): Distance = sqrt(4+1) = sqrt(5) ≈ 2.236
4. Compare (3,4) and (6,8): Distance = sqrt(9+16) = 5
5. Compare (3,4) and (2,1): Distance = sqrt(1+9) = sqrt(10) ≈ 3.162
6. Compare (6,8) and (2,1): Distance = sqrt(16+49) = sqrt(65) ≈ 8.062

The smallest distance is ≈ 2.236, between (0,0) and (2,1).

Time and Space Complexity

Brute-force Approach:
- Time Complexity: O(n²), because we check every pair of points. For n points, there are n(n-1)/2 pairs.
- Space Complexity: O(1), since we only use a few variables for tracking the minimum distance.

Optimized Approach (Divide-and-Conquer):
- Time Complexity: O(n log n), but the implementation is much more complex.
- Space Complexity: O(n), due to recursion and auxiliary arrays.

For most practical cases and coding interviews, the brute-force method is preferred for its simplicity.

Summary

To solve the "Shortest Distance in a Plane" problem, we compare every pair of points and compute their Euclidean distance, keeping track of the minimum found. This approach is straightforward, easy to implement, and efficient enough for moderate input sizes. While more advanced algorithms exist for very large inputs, the brute-force method is often the best choice for clarity and reliability. The key insight is to systematically check all possibilities while minimizing unnecessary computations.

Code Implementation

import math
from typing import List

def shortestDistance(points: List[List[int]]) -> float:
    min_dist = float('inf')
    n = len(points)
    for i in range(n):
        for j in range(i+1, n):
            dx = points[i][0] - points[j][0]
            dy = points[i][1] - points[j][1]
            dist = math.hypot(dx, dy)
            if dist < min_dist:
                min_dist = dist
    return min_dist
      

#include <vector>
#include <cmath>
#include <limits>
using namespace std;

double shortestDistance(vector<vector<int>>& points) {
    double minDist = numeric_limits<double>::infinity();
    int n = points.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int dx = points[i][0] - points[j][0];
            int dy = points[i][1] - points[j][1];
            double dist = hypot(dx, dy);
            if (dist < minDist)
                minDist = dist;
        }
    }
    return minDist;
}
      

import java.util.*;

public class Solution {
    public double shortestDistance(int[][] points) {
        double minDist = Double.POSITIVE_INFINITY;
        int n = points.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                double dist = Math.hypot(dx, dy);
                if (dist < minDist)
                    minDist = dist;
            }
        }
        return minDist;
    }
}
      

/**
 * @param {number[][]} points
 * @return {number}
 */
function shortestDistance(points) {
    let minDist = Infinity;
    let n = points.length;
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            let dx = points[i][0] - points[j][0];
            let dy = points[i][1] - points[j][1];
            let dist = Math.hypot(dx, dy);
            if (dist < minDist)
                minDist = dist;
        }
    }
    return minDist;
}