Last Updated: 10 Sep, 2021

Batch Photography

Hard

Asked in companies

Solve now

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’.

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

Instead of linear searching the ‘error’, we can use binary search to find the optimal error and check if it is valid using the same dynamic programming approach as discussed in approach 1.

The steps are as follows:

Sort the array.
We initialize ‘low’ as 0.
We initialize a ‘high’ as photos[N - 1] - photos[0].
We initialize ‘ans’ as ‘high’.
Traverse the array while ‘low’ <= ‘high’.
- Initialize ‘mid’ = (low + high) / 2.
- Call the function ‘check’ passing the parameter ‘error’ = ‘mid’.
- If the function returns true.
  - Update ‘ans’ as ‘mid’.
  - Update ‘high’ as ‘mid’ - 1.
- Else
  - Update ‘low’ as ‘mid’ + 1.
Return ‘ans’.

Solve now