Minimum Absolute Difference in Latency

In this problem, we need to find all pairs of latency values that share the smallest possible absolute difference. Because the input can contain duplicates and large values, we need an efficient way to compare numbers without checking every possible combination.

Overview

The "absolute difference" between two numbers $a$ and $b$ is simply $|a - b|$. In a sorted list, the minimum absolute difference must occur between two adjacent elements. This is the key insight that allows us to move from an $O(N^2)$ comparison strategy to an $O(N \log N)$ sorting strategy.

Brute Force

The brute force approach involves checking every possible pair $(i, j)$ where $i \neq j$. For each pair, we calculate the absolute difference. We keep track of the minimum difference found so far and store the pairs that match it. If we find a new, smaller difference, we discard all previous pairs and start a new collection.

To satisfy the requirement that $a \leq b$ and pairs are sorted, we would still need to sort the input or sort each pair and the final list.

def min_absolute_difference(latencies: list[int]) -> list[list[int]]:
    n = len(latencies)
    # Sort first to easily handle the a <= b requirement and result ordering
    latencies.sort()
    
    min_diff = float('inf')
    result = []
    
    for i in range(n):
        for j in range(i + 1, n):
            diff = latencies[j] - latencies[i]
            if diff < min_diff:
                min_diff = diff
                result = [[latencies[i], latencies[j]]]
            elif diff == min_diff:
                result.append([latencies[i], latencies[j]])
                
    return result

Time complexity: O(N^2) — We iterate through all possible pairs in the array using nested loops. Space complexity: O(N^2) — In the worst case (though unlikely for min difference), the result list could store many pairs.

Optimal Approach

The optimal approach leverages Sorting. Once the latencies array is sorted, the two numbers that produce the minimum difference are guaranteed to be neighbors.

1. Sort the latencies array in ascending order.
2. First Pass: Iterate through the sorted array once to find the global minimum difference between any two adjacent elements latencies[i] and latencies[i+1].
3. Second Pass: Iterate again and collect all adjacent pairs whose difference equals the minimum difference identified in step 2.

Since the array is sorted, any pair [latencies[i], latencies[i+1]] already satisfies $a \leq b$, and the resulting list will naturally be sorted by the first element.

def min_absolute_difference(latencies: list[int]) -> list[list[int]]:
    # 1. Sort the array
    latencies.sort()
    
    # 2. Find the minimum absolute difference
    min_diff = float('inf')
    for i in range(len(latencies) - 1):
        diff = latencies[i+1] - latencies[i]
        if diff < min_diff:
            min_diff = diff
            
    # 3. Collect all pairs with the minimum difference
    result = []
    for i in range(len(latencies) - 1):
        if latencies[i+1] - latencies[i] == min_diff:
            result.append([latencies[i], latencies[i+1]])
            
    return result

Time complexity: O(N log N) — Sorting the array takes $O(N \log N)$, followed by two linear passes of $O(N)$. Space complexity: O(N) — Apart from the output list, we only use a constant amount of extra space. Some sorting algorithms use $O(\log N)$ or $O(N)$ space internally.

Why This Works

Consider three sorted numbers $x < y < z$. The difference between $x$ and $z$ is $(z - y) + (y - x)$. Since all values are non-negative, the difference between $x$ and $z$ will always be greater than or equal to the difference between the adjacent pairs $(x, y)$ or $(y, z)$. Therefore, we never need to look beyond immediate neighbors in a sorted list to find the minimum difference.

Edge Cases

• Duplicates: If latencies = [1, 1, 1], the minimum difference is $0$. The algorithm correctly identifies pairs at indices $(0,1)$ and $(1,2)$, returning [[1, 1], [1, 1]].
• Large Values: With values up to $10^9$, sorting is efficient while a nested loop would likely time out given $N = 10^5$.

Fast