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?
Problem Overview: The table Point stores integer coordinates representing points on a 1D number line. The task is to compute the minimum absolute distance between any two different points. The result is a single number representing the closest pair of coordinates.
Approach 1: Self-Join (O(n^2) time, O(1) extra space)
This method compares every point with every other point using a SQL self join. Join the table to itself as p1 and p2, restrict the pairs with p1.x < p2.x to avoid duplicate and zero-distance comparisons, and compute ABS(p1.x - p2.x). The minimum of these values gives the shortest distance. Conceptually, this is the brute-force solution: enumerate all pairs and pick the smallest difference. The query is easy to reason about and works on any SQL system that supports joins, but the pairwise comparison results in quadratic work when the table grows large.
This approach relies on basic relational operations like joins and filtering, which are core concepts in database queries and SQL. It’s a good baseline when window functions are unavailable.
Approach 2: Window Function (O(n log n) time, O(1) extra space)
The key observation: the closest pair must appear next to each other after sorting the coordinates. Instead of comparing all pairs, sort by x and compute the difference between each row and the next row. In MySQL, the LEAD() window function retrieves the next coordinate in sorted order. Calculate LEAD(x) OVER (ORDER BY x) - x and then take the minimum value across all rows.
This reduces the work dramatically because each point is compared only with its immediate neighbor in the sorted sequence. The database performs a sort (typically O(n log n)), then a single linear scan using the window function. Window functions are designed exactly for these adjacent-row comparisons and are widely used in analytical queries involving ranking, gaps, or differences. See related concepts under window functions.
Recommended for interviews: The window function approach is the cleanest and most scalable solution. It demonstrates that you understand the key insight: once sorted, the smallest difference must occur between adjacent values. The self-join solution still shows a solid baseline understanding of SQL joins and brute-force comparison, but interviewers generally expect the optimized window-function solution when the database supports it.
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
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.
MySQL
| Approach | Complexity |
|---|---|
| Self-Join | — |
| Window Function | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self-Join | O(n^2) | O(1) | When window functions are unavailable or when demonstrating the brute-force pair comparison approach |
| Window Function with LEAD() | O(n log n) | O(1) | Preferred solution in MySQL or modern SQL systems where sorting and adjacent-row comparison are efficient |
LeetCode Interview SQL Question with Detailed Explanation | Practice SQL | LeetCode 613 • Everyday Data Science • 16,871 views views
Watch 1 more video solutions →Practice Shortest Distance in a Line with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor