Neighbours after sorting
Once sorted, the closest values sit side by side. About 8 minutes.
Sorting brings close values together
In 9, 1, 14, 4, 11 the two closest values are 9 and 11, but they are far apart in the list. Sort it and you get 1, 4, 9, 11, 14, and now they stand side by side, like two friends who finally get seated together.
In a sorted list the closest pair is always a pair of neighbours.
4 − 1 = 3. Best so far: 3.
Then one walk over the neighbours
Walk along the sorted list and, at each step, measure the gap between a value and the one just before it. Keep the smallest gap you have seen. That is n − 1 checks instead of comparing every pair.
The same trick finds repeats: equal values end up next to each other, with a gap of 0.
nums.sort()
best = nums[1] - nums[0]
for i in range(2, len(nums)):
gap = nums[i] - nums[i - 1]
best = min(best, gap)
return bestnums is sorted: [2, 5, 6, 10]. Which pairs do you need to check to find the closest two?
- AOnly 2 and 5, 5 and 6, 6 and 10
- BAll six pairs
- COnly 2 and 10
Show the answer
Only 2 and 5, 5 and 6, 6 and 10. In a sorted list the closest pair is always two neighbours, so three checks are enough.
The closest pair
Return the smallest difference between two values in nums (the bigger one minus the smaller one). The two values must be at different positions. nums has at least two values.
nums = [9, 1, 14, 4, 11] → 2
2 ≤ n ≤ 500,000 · 0 ≤ each value ≤ 1,000,000,000