Alice has a collection of N numbers. She would like to place them on a number line. She places each of the N numbers on the point corresponding to its value on the number line. Now she wonders, what’s the size of the smallest interval on the number line such that there are at least K numbers from her collection on that interval?
The first line of the input contains two integers N and K. The next line consists of N space separated integers denoting Alice’s numbers. Let, ai be the ith number on this line.
1 ≤ N ≤ 105
1 ≤ K ≤ N
1 ≤ ai ≤ 109
In a single line, print the size of the smallest interval on the number line where at least K integers from Alice’s collection can be found.
5 3 17 12 5 4 8
6 2 16 5 7 4 4 8
Explanation of Sample Case 1: The desired interval is [4,8] which contains 4, 5 and 8. The size of this interval is 4.
Explanation of Sample Case 2: The desired interval is [4,4] which contains 4 and 4. The size of this interval is 0.
Login to submit
Sort the array in non-decreasing order. Now notice that, the smallest interval that starts at ai and... Read more...