613. Shortest Distance in a Line 🔒

Description

Table: Point

+-------------+------+
| Column Name | Type |
+-------------+------+
| x           | int  |
+-------------+------+
In SQL, x is the primary key column for this table.
Each row of this table indicates the position of a point on the X-axis.

Find the shortest distance between any two points from the Point table.

It is guaranteed that the Point table contains at least two rows.

The result format is in the following example.

Example 1:

Input: 
Point table:
+----+
| x  |
+----+
| -1 |
| 0  |
| 2  |
+----+
Output: 
+----------+
| shortest |
+----------+
| 1        |
+----------+
Explanation: The shortest distance is between points -1 and 0 which is |(-1) - 0| = 1.

Follow up: How could you optimize your solution if the Point table is ordered in ascending order?

Solutions

Solution 1: Self-Join

Thinking

On a line the shortest distance is the minimum positive difference of two points. A self-join with p1.x < p2.x and MIN(p2.x - p1.x) is enough.

We can use a self-join to join each point in the table with the larger points, and then calculate the distance between the two points. Finally, we can take the minimum distance.

MySQL

# Write your MySQL query statement below
SELECT MIN(p2.x - p1.x) AS shortest
FROM
    Point AS p1
    JOIN Point AS p2 ON p1.x < p2.x;

Solution 2: Window Function

Thinking

The minimum must occur between neighbors after sorting, so a full join is unnecessary. LAG(x) yields the previous point; the smallest positive gap is the answer.

We can use a window function to sort the points in the table by their \(x\) values, and then calculate the distance between adjacent points. Finally, we can take the minimum distance.