We’ve seen multiple sorting algorithms, implemented them, and used them to solve various problems. Here’s another interesting sorting problem. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let’s get started!

Problem Statement

We’re given an array with $n$ numbers. We need to choose K numbers from the array such that the difference between the maximum and the minimum values from the array is minimized.

Constraints: $n \leq 1000000$ and $k \leq n$.

IO description

Input description: The first line contains the number of test cases T. Each test case consists of two lines. The first line has two numbers $n$ (size of array) and $k$ (number of numbers of choose). The second line has a list of $n$ numbers separated by spaces (" ").

Sample Input:

2
5 2
183 332 272 301 190
5 3
183 332 272 301 190

Output description: Output should contain T lines. Each line should contain the answer for the respective test case - the minimum difference between the maximum and minimum values for some $k$ numbers from the input.

Sample output:

7
60

Explanation:

In the first test case, the set {183, 190} achieves a difference of 7. No other set of size 2 has a smaller difference.

In the second test case, the set {332, 272, 301} achieves a difference of 332 - 272 = 60. No other set of size 3 has a smaller difference.

Submitting your solution

Once you are confidant of your solution, download the input file and run your code with the provided input. Then take the quiz!

Progressive ‘hint-by-hint’ solution

Only look at the hints if you can’t solve the problem for at-least 20-minutes. Read only one hint that you could not figure out on your own. Then spend at-least 20-minutes trying to solve the problem again.

Hint 1:

Trying out every possible subset of $k$ numbers is extremely slow. What can we do to improve the solution?

Hint 2:

Suppose we sort all numbers in the array. What kind of subsets do we need to consider?

Full solution

The solution for this assignment is included at the end of the quiz. The code executes in ~2 seconds. If you implemented your solution in C++ or Java, you should expect your solution to run at-least 5x faster.