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:
25 2183 332 272 301 1905 3183 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:
760
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.