values of non-negative integers. For every pair of positions i < j, take the gap |values[i] - values[j]|. There are n·(n−1)/2 such pairs, where n is the length of the array.
Write all those gaps down in non-decreasing order (equal gaps of different pairs count separately) and return the one in position k, counting from 1.
Checking every pair takes O(n² log n); try to do better.values=[7, 2, 9, 4], k=3 → 3
The six pairs have gaps |7−2| = 5, |7−9| = 2, |7−4| = 3, |2−9| = 7, |2−4| = 2, |9−4| = 5. Sorted: 2, 2, 3, 5, 5, 7, so the third one is 3.
values=[5, 5, 5], k=3 → 0
All three pairs are made of equal numbers, so every gap is 0.
values=[10, 1], k=1 → 9
There is only one pair, and its gap is 9.
values=[7, 2, 9, 4], k=3
3
Run checks the first 3 tests in your browser. Submit checks all 73 tests on the server, hidden ones included.