256. Closest Two Values
Core1000 ms256 MBSolved by 0%
Print the smallest absolute difference between any two of n integers.
Checking every pair is n(n-1)/2 comparisons, which at 200000 is twenty
billion and will not finish.
Sort first, and the closest two values must end up next to each other. That reduces the answer to a single sweep over adjacent pairs, because any pair further apart in the sorted order differs by at least as much.
Constraints - `2 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer, the smallest absolute difference between two values.
Input4
3 8 15 17
Output2
Notehas its closest pair at the end of the sorted order
Input2
1 2
Output1
Noteis the smallest possible input
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.