Minimum Absolute Difference Between Two Values - Solution & Explanation

Problem Overview: Given a list of numbers, you need the smallest absolute difference between any pair of values. The task is simply to find two elements a and b such that |a - b| is minimized.

Approach 1: Brute Force (O(n²) time, O(1) space)

The straightforward method checks every pair of elements. Use two nested loops, compute abs(nums[i] - nums[j]) for all i < j, and track the minimum difference found. This guarantees the correct result but performs n*(n-1)/2 comparisons, which becomes expensive as the array grows. The approach works for small inputs and helps verify correctness during early implementation.

Approach 2: Sort + Single Pass (O(n log n) time, O(1) extra space)

A key observation: the smallest absolute difference must occur between two numbers that are closest in sorted order. After sorting the array, iterate once and compute the difference between adjacent elements only. Maintain a running minimum while scanning from left to right. Sorting takes O(n log n), and the single pass afterward takes O(n), giving an overall complexity of O(n log n) with constant extra space if sorting is done in place.

This approach relies on properties of ordered values: if a ≤ b ≤ c, then |a - c| cannot be smaller than both |a - b| and |b - c|. Because of that, checking only adjacent elements is sufficient.

Problems like this often appear in interviews when discussing arrays and sorting. The optimized method also reflects a common pattern: transform the data structure (sorting) so the final computation becomes a simple linear scan, similar to techniques used in greedy strategies.

Recommended for interviews: Interviewers expect the sort + single pass solution. Starting with brute force demonstrates that you understand the definition of the problem. Moving to the sorted scan shows you can reduce comparisons by exploiting ordering, which is the key insight.