# 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. ([leetcode.com](https://leetcode.com/problems/shortest-distance-in-a-plane/?utm_source=chatgpt.com))

## Input and Output

Input table:

```sql
Point2D
```

Output column:

```sql
shortest
```

Distance formula between two points:

For points:

```text
(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:

```text
(-1, -1) and (0, 0)
```

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

Approximately:

```text
1.41
```

Between:

```text
(-1, -1) and (-1, -2)
```

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

Between:

```text
(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:

```text
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:

```sql
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

```sql
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:

```sql
FROM Point2D AS p1
JOIN Point2D AS p2
```

The join condition removes duplicate orderings and self-pairs:

```sql
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:

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

Then we take the minimum distance:

```sql
MIN(...)
```

Finally, round the result:

```sql
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:

```sql
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:

```sql
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:

```sql
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 |