Description

Table: Point

Column NameType
xint
  • 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.

Problem Statement

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?

Solution

This problem is similar to 612. Shortest Distance in a Plane.

First, you need to join Point table with itself in order to find two different points from the same table. The join condition will make sure that you don’t end up comparing the same point with itself.

1Point p1
2JOIN Point p2
3ON p1.x != p2.x

Once you’ve got two points, you need to calculate the distance between them. The distance can be positive or negative, but we need to calculate the absolute value between those two points on a line. So, we can use ABS(p1.x - p2.x).

The final solution will be as below.

1SELECT 
2    MIN(ABS(p1.x - p2.x)) AS shortest
3    FROM Point p1
4    JOIN Point p2
5    ON p1.x != p2.x;