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.

Description Solution Video 9:04

613. Shortest Distance in a Line

Easy80.0% acceptancePremium elsewhere, free here

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?

Topics

Database

9:04

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1

Input

{"headers":{"Point":["x"]},"rows":{"Point":[[-1],[0],[2]]}}

Your code is saved on this device.Solution