A jeweler is assembling a matched bracelet from a tray of n loose gems, each with a measured purity rating. To finish the piece the jeweler must select exactly k of the gems; the bracelet only looks matched if the purity ratings of the chosen gems are as close together as possible, judged by the gap between the highest and the lowest purity rating among the k selected gems. Given the purity ratings of all the gems on the tray, find the smallest possible value of (highest selected purity) minus (lowest selected purity) over every way of choosing exactly k of them.
The first line contains two space-separated integers n and k -- the number of gems on the tray and the number of gems that must be selected. The second line contains n space-separated integers, the purity ratings of the gems in tray order.
Print a single integer: the minimum possible difference between the highest and lowest purity rating among any k selected gems.
1 <= k <= n <= 100000 0 <= purity rating <= 1000000, for every gem.
Example 1
Input
6 3 90 55 88 95 53 42
Expected
7
Explanation
Sorting the purities gives 42, 53, 55, 88, 90, 95. Checking every run of three consecutive values in that sorted order, the tightest cluster is {88, 90, 95} with a spread of 95 - 88 = 7, which is smaller than any other run of three, so 7 is the minimum possible spread.
Example 2
Input
5 1 10 20 30 40 50
Expected
0
Explanation
With k = 1 the jeweler selects a single gem, whose highest and lowest purity are the same value, so the spread is always 0 no matter which gem is chosen.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →