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.

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:

Point

Output column:

shortest

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

ABS(a - b)

Example

Input:

Pair distances:

The shortest distance is 1.

Output:

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:

Then we compute:

p2.x - p1.x

We only keep pairs where:

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:

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

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:

FROM Point AS p1
JOIN Point AS p2

The join condition keeps only ordered pairs:

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:

p2.x - p1.x

Finally, MIN returns the shortest distance:

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.

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.

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:

CREATE TABLE Point (
    x INT PRIMARY KEY
);

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

Expected output:

Additional case:

TRUNCATE TABLE Point;

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

Adjacent sorted distances:

Expected output: