LeetCode Problem 613

Difficulty: 🟢 Easy
Topics: Database

Solution

LeetCode 613, Shortest Distance in a Line

Problem Understanding

This problem gives us a database table named Point that contains integer coordinates on the X-axis. Each row represents one point, and the column x is unique because it is the primary key.

The task is to compute the smallest absolute distance between any two points in the table.

Mathematically, for every pair of points (a, b), we want to calculate:

$$|a - b|$$

and return the minimum value among all possible pairs.

For example, if the points are:

-1, 0, 2

the pairwise distances are:

|-1 - 0| = 1
|-1 - 2| = 3
|0 - 2| = 2

The minimum distance is 1, so the output should contain:

+----------+
| shortest |
+----------+
| 1        |
+----------+

The important observation is that the table contains points on a one dimensional line. In one dimension, the closest pair of points must be adjacent after sorting the values.

The follow up asks how we could optimize the solution if the table is already sorted in ascending order. This hint strongly suggests that sorting or adjacency is the key insight.

There are several edge cases worth considering:

• The table may contain only two points, in which case the answer is simply their distance.
• The points may include negative numbers, so absolute difference is necessary.
• The points are unique because x is a primary key, so duplicate coordinates cannot occur.
• The smallest distance may appear between any neighboring values after sorting, not necessarily the first or last pair.

Approaches

Brute Force Approach

The most direct solution is to compare every pair of points.

For each point p1, we compare it against every other point p2, compute:

$$|p1.x - p2.x|$$

and keep track of the minimum value found.

This works because it exhaustively checks all possible pairs, guaranteeing that the minimum distance is discovered.

However, if there are n points, there are:

$$\frac{n(n-1)}{2}$$

possible pairs. This results in quadratic time complexity, which becomes inefficient for large datasets.

In SQL, this can be implemented with a self join:

SELECT MIN(ABS(p1.x - p2.x)) AS shortest
FROM Point p1
JOIN Point p2
ON p1.x < p2.x;

Although correct, this approach performs unnecessary comparisons.

Optimal Approach

The key insight is that after sorting the points, the minimum distance can only occur between adjacent points.

Consider sorted values:

x1 < x2 < x3 < x4

If x1 and x3 were the closest pair, then:

x2 - x1 < x3 - x1

which means x1 and x3 cannot actually be the closest pair because x2 lies between them.

Therefore, we only need to compare neighboring points after sorting.

In SQL, we can achieve this efficiently using the LEAD() window function:

SELECT MIN(next_x - x) AS shortest
FROM (
    SELECT x,
           LEAD(x) OVER (ORDER BY x) AS next_x
    FROM Point
) t
WHERE next_x IS NOT NULL;

This approach avoids unnecessary pair comparisons and directly computes adjacent differences.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Compares every pair of points
Optimal	O(n log n)	O(1) or O(n)	Sorts points and checks adjacent differences only

Algorithm Walkthrough

Optimal Algorithm

1. Sort all points in ascending order by their x coordinate.

Sorting is important because the closest pair of points in one dimension must appear next to each other after ordering. 2. Iterate through the sorted points from left to right.

For each point, compare it only with the next point in the sorted order. 3. Compute the difference between adjacent points.

Since the array is sorted:

next_x - current_x

is always non negative, so no absolute value is needed. 4. Maintain a running minimum distance.

Each time a smaller adjacent difference is found, update the answer. 5. Return the smallest distance discovered during traversal.

Why it works

The algorithm relies on a fundamental ordering property of points on a line. After sorting, any non adjacent pair must have at least one point between them. That intermediate point creates a smaller or equal distance than the non adjacent pair. Therefore, the global minimum distance must occur between neighboring points in sorted order.

Because the algorithm checks all adjacent pairs exactly once, it is guaranteed to find the correct minimum distance.

Python Solution

class Solution:
    def shortestDistance(self, points: List[int]) -> int:
        points.sort()

        minimum_distance = float("inf")

        for index in range(1, len(points)):
            current_distance = points[index] - points[index - 1]
            minimum_distance = min(minimum_distance, current_distance)

        return minimum_distance

The implementation begins by sorting the list of points. This ensures that the closest pair, if it exists, must appear consecutively.

The variable minimum_distance stores the best answer found so far. It is initialized to infinity so that any real distance will replace it during the first comparison.

The loop starts at index 1 because each point is compared with the previous point. Since the list is sorted, subtracting consecutive elements directly gives the distance between them.

For every adjacent pair, the algorithm computes the distance and updates the running minimum.

Finally, the smallest discovered distance is returned.

Although the original LeetCode problem is categorized under Database and expects SQL, this Python implementation demonstrates the core algorithmic idea clearly.

Go Solution

package main

import (
	"math"
	"sort"
)

func shortestDistance(points []int) int {
	sort.Ints(points)

	minimumDistance := math.MaxInt32

	for i := 1; i < len(points); i++ {
		currentDistance := points[i] - points[i-1]

		if currentDistance < minimumDistance {
			minimumDistance = currentDistance
		}
	}

	return minimumDistance
}

The Go implementation follows the same logic as the Python version.

The slice is sorted using sort.Ints. Since Go does not have a built in infinity value for integers, math.MaxInt32 is used as the initial large value for minimumDistance.

The loop compares each element with its previous neighbor and updates the minimum difference when a smaller value is found.

Because the points are sorted first, subtraction always produces a non negative value.

Worked Examples

Example 1

Input:

[-1, 0, 2]

Step 1: Sort the points

The points are already sorted:

[-1, 0, 2]

Step 2: Compare adjacent points

Index	Current Point	Previous Point	Distance	Minimum So Far
1	0	-1	1	1
2	2	0	2	1

The final answer is:

1

because the smallest adjacent difference is 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(n)	Depends on the sorting implementation

The traversal after sorting is linear because each adjacent pair is checked exactly once.

The dominant cost comes from sorting the points. Most sorting algorithms require O(n log n) time.

The extra space depends on the language and sorting implementation. Some sorting algorithms operate in place, while others allocate temporary memory.

Test Cases

def shortest_distance(points):
    points.sort()

    minimum_distance = float("inf")

    for i in range(1, len(points)):
        minimum_distance = min(
            minimum_distance,
            points[i] - points[i - 1]
        )

    return minimum_distance

# Basic example from the problem statement
assert shortest_distance([-1, 0, 2]) == 1

# Only two points
assert shortest_distance([5, 10]) == 5

# Negative numbers
assert shortest_distance([-10, -3, -1]) == 2

# Already sorted input
assert shortest_distance([1, 3, 8, 12]) == 2

# Unsorted input
assert shortest_distance([8, 1, 12, 3]) == 2

# Large gaps
assert shortest_distance([1, 100, 1000]) == 99

# Consecutive integers
assert shortest_distance([4, 5, 6, 7]) == 1

# Minimum distance at the end
assert shortest_distance([1, 10, 20, 21]) == 1

# Minimum distance at the beginning
assert shortest_distance([1, 2, 10, 20]) == 1

# Mixed positive and negative values
assert shortest_distance([-100, -50, 0, 49]) == 49

Test	Why
[-1, 0, 2]	Validates the provided example
[5, 10]	Smallest valid input size
[-10, -3, -1]	Ensures negative values work correctly
[1, 3, 8, 12]	Tests already sorted input
[8, 1, 12, 3]	Ensures sorting is handled properly
[1, 100, 1000]	Tests large gaps between values
[4, 5, 6, 7]	Verifies consecutive values
[1, 10, 20, 21]	Minimum distance appears near the end
[1, 2, 10, 20]	Minimum distance appears near the beginning
[-100, -50, 0, 49]	Tests mixed negative and positive numbers

Edge Cases

Only Two Points

The smallest valid input contains exactly two points. In this scenario, there is only one possible pair, so the algorithm must correctly return their distance without additional assumptions.

The implementation handles this naturally because the loop executes exactly once and computes the difference between the two sorted values.

Negative Coordinates

Points can be negative because they represent positions on the X-axis. A naive implementation that assumes positive numbers could produce incorrect results.

Sorting ensures the values are ordered numerically, and subtracting adjacent sorted values always produces the correct non negative distance.

Unsorted Input

The input points may not initially appear in ascending order. If the algorithm compared only neighboring elements without sorting first, it could miss the true minimum distance.

For example:

[8, 1, 3]

The actual shortest distance is between 1 and 3, not between the original adjacent values.

The implementation avoids this issue by sorting before any comparisons occur.

Large Coordinate Gaps

Some inputs may contain very large distances between most points, with only one small gap hidden somewhere in the list.

Because the algorithm systematically checks every adjacent pair after sorting, it cannot miss the true minimum regardless of how unevenly spaced the coordinates are.