LeetCode 612: Shortest Distance in a Plane

Problem Restatement

We are given a table called Point2D.

Each row represents one point in a 2D plane.

Column	Type	Meaning
x	decimal	x-coordinate
y	decimal	y-coordinate

We need to find the shortest Euclidean distance between any two distinct points.

The result should contain one column:

Column	Meaning
shortest	Minimum distance between any pair of points

The final answer should be rounded to two decimal places.

The official problem asks for the shortest distance between any two points in the plane using Euclidean distance.

Input and Output

Input table:

Point2D

Output column:

shortest

Distance formula between two points:

For points:

(x1, y1)
(x2, y2)

the Euclidean distance is:

$$ d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $$

Example

Input:

x	y
-1	-1
0	0
-1	-2

Distances:

Between:

(-1, -1) and (0, 0)

genui{"math_block_widget_always_prefetch_v2":{"content":"\sqrt{((-1)-0)^2 + ((-1)-0)^2} = \sqrt{2}"} }

Approximately:

1.41

Between:

(-1, -1) and (-1, -2)

genui{"math_block_widget_always_prefetch_v2":{"content":"\sqrt{((-1)-(-1))^2 + ((-1)-(-2))^2} = 1"} }

Between:

(0, 0) and (-1, -2)

genui{"math_block_widget_always_prefetch_v2":{"content":"\sqrt{(0-(-1))^2 + (0-(-2))^2} = \sqrt{5}"} }

The minimum distance is:

1.00

Output:

shortest
1.00

First Thought: Compare Every Pair of Points

The distance depends on pairs of points.

So the direct approach is:

1. Generate all distinct pairs of points.
2. Compute the Euclidean distance for each pair.
3. Return the minimum value.

In SQL, generating all pairs naturally suggests a self join.

Key Insight

If we join the table with itself, we can treat:

Alias	Meaning
p1	First point
p2	Second point

Then compute the Euclidean distance between them.

We must avoid:

Invalid Pair	Reason
A point with itself	Distance would always be 0
Duplicate pair ordering	(A, B) and (B, A) are the same pair

The cleanest way is to require:

p1.x < p2.x
OR (p1.x = p2.x AND p1.y < p2.y)

This guarantees:

Property	Result
No self-pairs	Same point excluded
No duplicate orderings	Only one ordering kept

Algorithm

Perform a self join of Point2D.

For every unique pair of points:

1. Compute the Euclidean distance.
2. Take the minimum distance.
3. Round the result to two decimal places.

SQL Solution

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

Code Explanation

The query creates all unique point pairs:

FROM Point2D AS p1
JOIN Point2D AS p2

The join condition removes duplicate orderings and self-pairs:

ON (
    p1.x < p2.x
    OR (
        p1.x = p2.x
        AND p1.y < p2.y
    )
)

This means:

Allowed	Rejected
(A, B)	(B, A)
Different points	Same point

For each valid pair, we compute the Euclidean distance:

$$ \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2} $$

SQL implementation:

SQRT(
    POW(p1.x - p2.x, 2) +
    POW(p1.y - p2.y, 2)
)

Then we take the minimum distance:

MIN(...)

Finally, round the result:

ROUND(..., 2)

Correctness

The self join generates every unordered pair of distinct points exactly once.

The join condition ensures:

Condition	Effect
Different coordinates	Excludes self-pairs
Lexicographic ordering	Avoids duplicate pair directions

For each generated pair, the query computes the exact Euclidean distance using the distance formula.

Since every valid point pair is considered exactly once, the MIN aggregation returns the smallest Euclidean distance among all pairs.

The final rounding step produces the required two-decimal-place output.

Therefore, the query correctly returns the shortest distance between any two points.

Complexity

Let n be the number of points.

Metric	Value	Why
Time	O(n^2)	Every point pair may be compared
Space	O(1) to O(n^2)	Depends on database join execution

The number of unique point pairs is:

$$ \frac{n(n-1)}{2} $$

so quadratic work is unavoidable in this direct approach.

Alternative: Use id

Some database versions include a unique row id.

Then the join becomes simpler:

SELECT
    ROUND(
        MIN(
            SQRT(
                POW(p1.x - p2.x, 2) +
                POW(p1.y - p2.y, 2)
            )
        ),
        2
    ) AS shortest
FROM Point2D AS p1
JOIN Point2D AS p2
    ON p1.id < p2.id;

Using unique ids is often cleaner than coordinate comparison.

Testing

Sample data:

CREATE TABLE Point2D (
    x DECIMAL(10, 2),
    y DECIMAL(10, 2)
);

INSERT INTO Point2D (x, y) VALUES
    (-1, -1),
    (0, 0),
    (-1, -2);

Expected output:

shortest
1.00

Additional case:

TRUNCATE TABLE Point2D;

INSERT INTO Point2D (x, y) VALUES
    (1, 1),
    (2, 2),
    (5, 5),
    (1, 2);

Distances:

Pair	Distance
(1,1) and (1,2)	1.00
(1,1) and (2,2)	1.41
(2,2) and (5,5)	4.24

Expected output:

shortest
1.00