Batch Photography

Hard
0/120
Average time to solve is 30m
profile
Contributed by
6 upvotes
Asked in companies
Wells FargoSamsung R&D Institute

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.

Detailed explanation ( Input/output format, Notes, Images )
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’.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= K <= N <= 10^4
1 <= photos[i] <= 10^9

Time Limit: 1 sec
Sample Input 1:
2
5 2
50 110 130 40 120
4 1
2 3 4 1
Sample Output 1:
20
0
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:
2
5 2
5 7 3 3 5
3 2
1 2 3
Sample Output 2:
2
2
Hint

If we fix the error, can we divide the array based on it?

Approaches (2)
Two Pointers

The first thing is that we can show that it is always beneficial to sort the array and then divide the array into subarrays. Then if we fix the error, we can use dynamic programming to divide the array into subarrays. 


 

Algorithm: 

Let us define a function ‘check’, which when passed a parameter ‘error’, returns whether the array can be divided such that its maximum error is less or equal to ‘error’.

  • Initialize an array ‘dp’ of size ‘N’ + 1 with false.
  • Dp[0] = true.
  • Now, the minimum position where we can first break the array is index ‘K’. So, if photo[k] - photo[0] <= ‘error’, change dp[k] = true. Else, there is no way to break, so we return false.
  • Let the current left side of the break be ‘curr’ = 1.
  • Traverse the array from i = ‘K’ + 1 to i = ‘N’
    • Now, with ‘i’ as the right end, we can keep ‘curr’ as the left end, only photo[i] - photo[curr] <= ‘error’. So, while this condition is false.
      • Increment ‘curr’.
    • Also, we can keep ‘curr’ as the left end, only when there is a valid right end of the previous subarray ar ‘curr’ - 1. So, while this condition is false.
      • Increment ‘curr’.
    • If curr <= i - k + 1
      • Dp[i] = true.
  • Return dp[N].


 

Now, we can check for which ‘error’, there are some valid breaks. We can find this using linear search, as we need the minimum such ‘error’. Note that the minimum error we can achieve is 0, and the maximum is the difference between the highest resolution and the lowest resolution in the entire array.


 

The steps are as follows:

  • Sort the array ‘photos’.
  • Traverse the array from ‘i’ = 0 to ‘i’ = photos[N - 1] - photos[0].
    • Call the function ‘check’, passing the parameter ‘error’ = i.
    • If the function returns true, we return i.
Time Complexity

O(N * L), where ‘N’ is the size of ‘photos’ and ‘L’ = max(photos) - min(photos).


 

For each possible error, we are traversing the array once to find if it is possible to divide the array. Thus, the overall complexity becomes O(N * L).


 

Space Complexity

O(N), where ‘N’ is the size of ‘photos’.


 

We are using an array of length ‘N’ to store the dp states. Thus, the overall complexity is O(N).


 

Code Solution
(100% EXP penalty)
Batch Photography
Full screen
Console