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.

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

The result should contain one column:

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. (leetcode.com)

Input and Output

Input table:

Point2D

Output column:

shortest

Distance formula between two points:

For points:

(x1, y1)
(x2, y2)

the Euclidean distance is:

Example

Input:

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:

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:

Then compute the Euclidean distance between them.

We must avoid:

The cleanest way is to require:

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

This guarantees:

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:

For each valid pair, we compute the Euclidean distance:

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:

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.

The number of unique point pairs is:

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:

Additional case:

TRUNCATE TABLE Point2D;

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

Distances:

Expected output: