Batch Photography

Difficulty: HARD
Contributed By
Avg. time to solve
30 min
Success Rate

Problem Statement

Alex has bought a new machine that does photocopies of photos in batches of minimum size ‘K’. Alex has ‘N’ photos, whose resolution is given in an integer array ‘photos’. The machine has some downsides as well. The error in photocopying a batch is the absolute difference between the highest resolution photo and the lowest resolution photo in the batch.

Now Alex will divide the photos into some groups of size at least ‘K’ and feed it to the machine. The maximum error is the maximum of the errors from each batch. He wants to minimize the maximum error. Can you help him divide the photos into batches efficiently and tell him the minimum maximum error he can achieve?

Example: Let the resolutions be [1, 5, 2] and K = 2. So there is only one way of dividing the array, which is a single group of all three elements. The error is therefore 5 - 1 = 4.

Input Format:
The first line contains ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the number of photos and the minimum size of each batch.

The second line of each test case contains an array ‘photos’ of ‘N’ space-separated integers, denoting the resolution of the ith photo.
Output Format:
For each test case, print an integer denoting the minimum ‘maximum error’.
You are not required to print the expected output. It has already been taken care of. Just implement the function.
1 <= T <= 10
1 <= K <= N <= 10^4
1 <= photos[i] <= 10^9

Time Limit: 1 sec
Sample Input 1:
5 2
50 110 130 40 120
4 1
2 3 4 1
Sample Output 1:
Explanation for Sample Input 1:
In the first test case, the photos should be split into 2 groups: [40, 50] and [110, 120, 130]. The processing time of the first group is 10, and the processing time of the second group is 20. The maximum between 10 and 20 is 20. It is impossible to split the photos into groups in such a way that the processing time of division is less than 20.
In the second test case, the photos should be split into four groups, each containing one photo. So the minimal possible processing time of a division is 0.
Sample Input 2:
5 2
5 7 3 3 5
3 2
1 2 3
Sample Output 2:
Reset Code
Full screen