Skip to main content
Talentd

Shortest Distance in a Line - Solution & Explanation

EasyPremiumFree on FleetCodeDatabase4 min read
Practice this problem

Problem Statement

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?

Approach Overview

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.

Approach 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.

Code

MySQL

MySQL

Try this approach in the editor →

Approach 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.

Code

MySQL

MySQL

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Self-Join—
Window Function—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self-JoinO(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

Video Solution

LeetCode Interview SQL Question with Detailed Explanation | Practice SQL | LeetCode 613 • Everyday Data Science • 17,924 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Shortest Distance in a Line easy or hard?
Shortest Distance in a Line is considered an easy SQL problem. The logic is straightforward once you realize the minimum difference must occur between adjacent values after sorting.
Shortest Distance in a Line Python/Java solution
The problem is primarily a SQL query question rather than a traditional algorithm problem in Python or Java. The logic can be replicated in code by sorting a list of integers and scanning adjacent elements to find the smallest difference in O(n log n) time.
How to solve Shortest Distance in a Line in O(n)?
If the points are already sorted by coordinate, you can compute the shortest distance in O(n). Scan the sorted list and track the minimum difference between consecutive values. In SQL, this idea is implemented using LEAD() or LAG() window functions after ordering the rows.
What is the best approach for Shortest Distance in a Line?
The window function approach using LEAD() is the most efficient and clean solution. Sort the coordinates by x, compute the difference between each row and the next row, and return the minimum difference. This reduces comparisons to adjacent elements only, giving roughly O(n log n) time due to sorting.
Is Shortest Distance in a Line asked at Google/Amazon/Meta?
Database and SQL problems similar to this appear in interviews at companies like Amazon, Google, and Meta for data engineering and backend roles. Interviewers often focus on SQL joins, aggregations, and window functions to test query optimization skills.
What data structure is used in Shortest Distance in a Line?
The problem mainly uses relational tables and SQL operations. Conceptually, the optimized solution relies on sorting and comparing adjacent values, which mirrors array processing after ordering the data.
What is the time complexity of Shortest Distance in a Line?
The self-join solution runs in O(n^2) time because it compares every pair of points. The optimized window function approach runs in about O(n log n) time due to sorting the coordinates before computing adjacent differences.

Ready to solve this problem?

Practice Shortest Distance in a Line with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary