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.
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
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.
1 2 3 4 5 |
|
Solution 2: Window Function
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.
1 2 3 4 5 |
|