Problem

Table: Point2D

1
2
3
4
5
6
7
8

+-------------+------+
| Column Name | Type |
+-------------+------+
| x           | int  |
| y           | int  |
+-------------+------+
(x, y) is the primary key column (combination of columns with unique values) for this table.
Each row of this table indicates the position of a point on the X-Y plane.

The distance between two points p1(x1, y1) and p2(x2, y2) is sqrt((x2 -x1)2 + (y2 - y1)2).

Write a solution to report the shortest distance between any two points from the Point2D table. Round the distance to two decimal points.

The result format is in the following example.

Examples

Example 1:

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

Input: 
Point2D table:
+----+----+
| x  | y  |
+----+----+
| -1 | -1 |
| 0  | 0  |
| -1 | -2 |
+----+----+
Output: 
+----------+
| shortest |
+----------+
| 1.00     |
+----------+
Explanation: The shortest distance is 1.00 from point (-1, -1) to (-1, 2).

Solution

Method 1 – SQL Self Join and Aggregation

Intuition

To find the shortest distance between any two points, we need to compute the distance for every unique pair of points in the table. By joining the table with itself and excluding pairs where both points are the same, we can calculate all possible distances and select the minimum.

Approach

  • Use a self join on the Point2D table to generate all pairs of points (p1, p2).
  • Exclude pairs where both points are the same (i.e., p1.x != p2.x or p1.y != p2.y).
  • Calculate the Euclidean distance for each pair using the formula: sqrt((x2-x1)^2 + (y2-y1)^2).
  • Use aggregation to find the minimum distance.
  • Round the result to two decimal places as required.

Code

1
2
3
4

SELECT ROUND(MIN(SQRT(POW(p1.x - p2.x, 2) + POW(p1.y - p2.y, 2))), 2) AS shortest
FROM Point2D p1
JOIN Point2D p2
  ON p1.x != p2.x OR p1.y != p2.y;
1
2
3
4

SELECT ROUND(MIN(SQRT(POWER(p1.x - p2.x, 2) + POWER(p1.y - p2.y, 2))), 2) AS shortest
FROM Point2D p1
JOIN Point2D p2
  ON p1.x != p2.x OR p1.y != p2.y;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import pandas as pd
import numpy as np

def shortest_distance(df: pd.DataFrame) -> float:
    points = df[['x', 'y']].values
    min_dist = float('inf')
    n = len(points)
    for i in range(n):
        for j in range(i+1, n):
            dist = np.sqrt((points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2)
            if dist < min_dist:
                min_dist = dist
    return round(min_dist, 2)

Complexity

  • ⏰ Time complexity: O(n^2), since we compare every pair of points.
  • 🧺 Space complexity: O(1) for SQL, O(n) for Python (to store points).