# LeetCode 613: Shortest Distance in a Line

## Problem Restatement

We are given a table called `Point`.

Each row stores one point on the X-axis.

| Column | Type | Meaning |
|---|---|---|
| `x` | int | Position of the point on the X-axis |

The column `x` is the primary key, so every point is unique.

We need to find the shortest distance between any two points. The official problem asks for the minimum distance between any two points from the `Point` table.

## Input and Output

Input table:

```sql
Point
```

Output column:

```sql
shortest
```

For two points `a` and `b` on a line, their distance is:

```text
ABS(a - b)
```

## Example

Input:

| x |
|---:|
| -1 |
| 0 |
| 2 |

Pair distances:

| Pair | Distance |
|---|---:|
| `-1` and `0` | `1` |
| `-1` and `2` | `3` |
| `0` and `2` | `2` |

The shortest distance is `1`.

Output:

| shortest |
|---:|
| 1 |

## First Thought: Compare Every Pair

The distance is defined between two points, so the direct SQL approach is to join the table with itself.

We can call the two copies:

| Alias | Meaning |
|---|---|
| `p1` | First point |
| `p2` | Second point |

Then we compute:

```sql
p2.x - p1.x
```

We only keep pairs where:

```sql
p1.x < p2.x
```

This avoids comparing a point with itself and avoids counting the same pair twice.

## Key Insight

Because points are on a one-dimensional line, if `p1.x < p2.x`, the distance is simply:

```sql
p2.x - p1.x
```

No `ABS` is needed when we force the smaller point to appear first.

Then the answer is the minimum of all such distances.

## Algorithm

Join `Point` with itself.

Keep only pairs where the first point is smaller than the second point.

Compute the distance for each pair.

Return the minimum distance as `shortest`.

## SQL Solution

```sql
SELECT
    MIN(p2.x - p1.x) AS shortest
FROM Point AS p1
JOIN Point AS p2
    ON p1.x < p2.x;
```

## Code Explanation

The self join creates pairs of points:

```sql
FROM Point AS p1
JOIN Point AS p2
```

The join condition keeps only ordered pairs:

```sql
ON p1.x < p2.x
```

This has two effects.

It excludes self-pairs such as `0` with `0`.

It also avoids duplicate pair orderings. For example, it keeps `-1, 0` but not `0, -1`.

For each remaining pair, the distance is:

```sql
p2.x - p1.x
```

Finally, `MIN` returns the shortest distance:

```sql
MIN(p2.x - p1.x) AS shortest
```

## Correctness

The join condition `p1.x < p2.x` generates every unordered pair of distinct points exactly once.

For each generated pair, `p2.x` is greater than `p1.x`, so `p2.x - p1.x` is exactly the distance between those two points.

Since every valid pair is considered once, taking the minimum of all computed distances returns the shortest distance between any two points.

Therefore, the query returns the required result.

## Complexity

Let `n` be the number of rows in `Point`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | The self join may compare every pair of points |
| Space | `O(1)` to `O(n^2)` | Depends on the database execution plan |

## Alternative: Window Function

If the points are sorted, the shortest distance must occur between two adjacent points in sorted order.

So we can compute the previous point with `LAG`.

```sql
WITH ordered_points AS (
    SELECT
        x,
        LAG(x) OVER (ORDER BY x) AS prev_x
    FROM Point
)
SELECT
    MIN(x - prev_x) AS shortest
FROM ordered_points
WHERE prev_x IS NOT NULL;
```

This is often more efficient because it only compares adjacent points after sorting.

## Testing

Sample data:

```sql
CREATE TABLE Point (
    x INT PRIMARY KEY
);

INSERT INTO Point (x) VALUES
    (-1),
    (0),
    (2);
```

Expected output:

| shortest |
|---:|
| 1 |

Additional case:

```sql
TRUNCATE TABLE Point;

INSERT INTO Point (x) VALUES
    (-10),
    (-3),
    (4),
    (6),
    (20);
```

Adjacent sorted distances:

| Pair | Distance |
|---|---:|
| `-10`, `-3` | 7 |
| `-3`, `4` | 7 |
| `4`, `6` | 2 |
| `6`, `20` | 14 |

Expected output:

| shortest |
|---:|
| 2 |