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:

Hint 2:

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.