Problem Description

Given a list of integers points that represent positions on a 1D line, find the shortest distance between any two different points. The distance between two points is the absolute difference of their values. You must not reuse the same point for both positions. The function should return the minimum such distance found.

• Input: An array points of length at least 2, where each element is an integer representing a position on the line.
• Output: An integer representing the smallest distance between any two distinct points.
• Constraints:
  • Each element in points is an integer.
  • There is at least one pair of different points.
  • You cannot use the same element twice for a pair.

Thought Process

The most straightforward way to solve this problem is to compare every pair of points and keep track of the minimum distance found. This brute-force approach checks all possible pairs, but quickly becomes inefficient as the number of points increases.

To optimize, notice that the minimum distance must exist between two numbers that are closest to each other on the line. If the points are sorted, the smallest gap will always be between two consecutive elements. This insight allows us to avoid checking every single pair and instead just look at adjacent elements in the sorted list.

In summary, the shift is from checking all pairs (brute-force) to sorting the array and checking only consecutive pairs (optimized).

Solution Approach

Here’s a step-by-step breakdown of the optimized algorithm:

1. Sort the points: Arrange the points array in non-decreasing order. Sorting ensures that the closest points are next to each other.
2. Initialize a minimum distance variable: Set it to a large value (like infinity) to start.
3. Iterate through the sorted array: For each pair of consecutive elements, compute the absolute difference.
4. Update the minimum: If the current difference is smaller than the minimum found so far, update the minimum.
5. Return the minimum distance: After checking all consecutive pairs, return the smallest difference found.

This method is efficient because sorting takes O(n log n) time, and the single pass to check differences is O(n).

Example Walkthrough

Input: points = [4, 2, 1, 3]

1. Sort the array: [1, 2, 3, 4]
2. Check differences:
   • Between 1 and 2: 2 - 1 = 1
   • Between 2 and 3: 3 - 2 = 1
   • Between 3 and 4: 4 - 3 = 1
3. Track the minimum: All differences are 1, so the minimum is 1.
4. Return: 1

The solution efficiently finds that the smallest distance between any two points is 1.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n²), since every pair is checked.
  • Space Complexity: O(1), only a variable for the minimum is required.
• Optimized approach (sorting + single pass):
  • Time Complexity: O(n log n), due to sorting. The single pass is O(n).
  • Space Complexity: O(1) or O(n) depending on the sort implementation. Most languages can sort in-place, so O(1) extra space is typical.

Summary

By recognizing that the minimum distance must be between consecutive elements after sorting, we reduce the problem from a quadratic to a near-linear solution. The key insight is that sorting brings the closest points together, allowing a single pass to find the answer efficiently. This approach is both elegant and practical, leveraging basic properties of numbers on a line.

Code Implementation

def shortestDistance(points):
    points.sort()
    min_dist = float('inf')
    for i in range(1, len(points)):
        min_dist = min(min_dist, points[i] - points[i-1])
    return min_dist
      

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int shortestDistance(vector<int>& points) {
    sort(points.begin(), points.end());
    int min_dist = INT_MAX;
    for (int i = 1; i < points.size(); ++i) {
        min_dist = min(min_dist, points[i] - points[i-1]);
    }
    return min_dist;
}
      

import java.util.Arrays;

public class Solution {
    public int shortestDistance(int[] points) {
        Arrays.sort(points);
        int minDist = Integer.MAX_VALUE;
        for (int i = 1; i < points.length; i++) {
            minDist = Math.min(minDist, points[i] - points[i-1]);
        }
        return minDist;
    }
}
      

function shortestDistance(points) {
    points.sort((a, b) => a - b);
    let minDist = Infinity;
    for (let i = 1; i < points.length; i++) {
        minDist = Math.min(minDist, points[i] - points[i - 1]);
    }
    return minDist;
}