Shortest Distance in a Plane - Solution & Explanation

Problem Overview: You have a table Point(x, y) representing coordinates on a 2D plane. The task is to compute the minimum Euclidean distance between any pair of distinct points and return the smallest value.

Approach 1: Cross Join All Point Pairs (O(n²) time, O(1) space)

The direct way is to compare every point with every other point. Use a self CROSS JOIN on the Point table and compute the Euclidean distance with SQRT(POW(x1-x2,2) + POW(y1-y2,2)). Filter out identical rows using a condition like p1.x != p2.x OR p1.y != p2.y. Then compute the minimum distance with MIN(). This approach is simple and works well when the dataset is small, but it generates duplicate comparisons (A→B and B→A), which doubles the number of calculated distances.

Approach 2: Self Join with Unique Pair Filtering (O(n²) time, O(1) space)

A better SQL formulation removes duplicate comparisons by enforcing a consistent ordering between points. Instead of comparing all pairs, restrict the join condition so each pair appears only once. A common trick is p1.x < p2.x OR (p1.x = p2.x AND p1.y < p2.y). This ensures the query evaluates only unique point pairs. The distance formula remains the same, and the result is aggregated with MIN() and rounded if required. This reduces redundant work while keeping the logic straightforward.

This problem is fundamentally a pairwise comparison task implemented with SQL joins. The key idea is that relational databases do not provide a built‑in geometric nearest‑neighbor operator for this schema, so you simulate it with a self join and a distance formula. The database engine evaluates every valid pair and keeps the smallest value.

Understanding how to structure self joins is essential for many SQL interview problems. You often join a table with itself to compare rows, compute differences, or detect relationships. This problem also reinforces how aggregation functions like MIN() work with derived calculations.

Conceptually, the solution combines three SQL ideas: a database self join, a computed expression for distance, and an aggregate function to select the smallest value. The join pattern is closely related to many classic SQL join interview questions where row‑to‑row comparisons are required.

Recommended for interviews: The unique pair self join approach is the expected solution. It shows you understand how to avoid duplicate comparisons while still evaluating all necessary point pairs. Starting with the naive cross join demonstrates the reasoning process, but the optimized join condition reflects stronger SQL problem‑solving skills.