Batch Photography
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

Question

Batch Photography

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

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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

Time Complexity: OtherExplanation:

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

Accepted Answer

Binary Search + Two pointers

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

Space Complexity: O(n)Explanation:

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

Time Complexity: OtherExplanation:

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

For a given error, it takes O(N) time to check if we can somehow divide the array. We are finding such a possibility by finding the error using binary search which takes log(L) time. Thus, the overall complexity is O(N * log L).

Java (SE 1.8)

/*

    Time Complexity: O(N * log L)

    Space Complexity: O(N)



    where N is the size of photos and L = max(photos) - min(photos).

*/





import java.util.*;



// Function to check the validity of some chosen maximum error.

public class Solution {



	public static boolean check(int error, int n, int k, int[] photos){

		boolean[] dp = new boolean[n + 1];

		dp[0] = true;

	

		// If the smallest cut is not possible, this error can not be achieved.

		if(photos[k] - photos[1] <= error){

			dp[k] = true;

		}

		else{

			return false;

		}

		// 'curr' stores the last left break.

		int curr = 1;

		

		// Traverse to check all possible right cuts.

		for(int i = k + 1; i <= n; i++){

			// Increment 'curr' till the error is larger.

			while(curr <= n && photos[i] - photos[curr] > error){

				curr += 1;

			}    

			// Find the smallest position where a new left cut is possible.

			while(curr <= n && !dp[curr - 1]){

				curr += 1;

			}

			// If this subarray is of minimum size, this cut is possible.

			if(curr <= i - k + 1){

				dp[i] = true;

			}

		}

		return dp[n];

	}

    public static int photography(int n, int k, int[] photos) {

        

        int[] newPhotos = new int[n + 1];

		for(int i = 1; i <= n; i++){

			newPhotos[i] = photos[i - 1];

		}

		Arrays.sort(newPhotos);



		// Binary search the error.

		int left = 0, right = newPhotos[n] - newPhotos[1];

		int ans = right;

		

		while (left <= right){

			int mid = (left + right)/ 2;

			int error = mid;

			// If this error is possible, we can try for smaller error.

			if (check(error, n, k, newPhotos)){

				right = mid - 1;

				ans = mid;

			}

			else{

				left = mid + 1;

			}

		}

		return ans;

    }

}

C++ (g++ 5.4)

/*
    Time Complexity: O(N * log L)
    Space Complexity: O(N)

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

// Function to check the validity of some chosen maximum error.
int check(int error, int n, int k, vector &photos){
    vector dp(n + 1, false);
    dp[0] = true;

    // If the smallest cut is not possible, this error can not be achieved.
    if(photos[k] - photos[1] <= error){
        dp[k] = true;
    }
    else{
        return false;
    }
    // 'curr' stores the last left break.
    int curr = 1;
    
    // Traverse to check all possible right cuts.
    for(int i = k + 1; i <= n; i++){
        // Increment 'curr' till the error is larger.
        while(curr <= n and photos[i] - photos[curr] > error){
            curr += 1;
        }    
        // Find the smallest position where a new left cut is possible.
        while(curr <= n and !dp[curr - 1]){
            curr += 1;
        }
        // If this subarray is of minimum size, this cut is possible.
        if(curr <= i - k + 1){
            dp[i] = true;
        }
    }
    return dp[n];
}    
int photography(int n, int k, vector &photos){
    
    // Sort the array photos.
    sort(photos.begin(), photos.end());
    photos.insert(photos.begin(), 0);

    // Binary search the error.
    int left = 0, right = photos[n] - photos[1];
    int ans = right;
    
    while (left <= right){
        int mid = (left + right)/ 2;
        int error = mid;
        // If this error is possible, we can try for smaller error.
        if (check(error, n, k, photos)){
            right = mid - 1;
            ans = mid;
        }
        else{
            left = mid + 1;
        }
    }
    return ans;
}

Python (3.5)

'''

    Time Complexity: O(N * log L)

    Space Complexity: O(N)



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

'''



def photography(n, k, photos):

    

    # Sort the array photos.

    photos.sort()

    photos = [0] + photos

    

    # Function to check the validity of some chosen maximum error.

    def check(error):

        dp = [False] * (n + 1)

        dp[0] = True

        

        # If the smallest cut is not possible, this error can not be achieved.

        if photos[k] - photos[1] <= error:

            dp[k] = True

        else:

            return False

        

        # 'curr' stores the last left break.

        curr = 1

        

        # Traverse to check all possible right cuts.

        for i in range(k + 1, n + 1):

            # Increment 'curr' till the error is larger.

            while curr <= n and photos[i] - photos[curr] > error:

                curr += 1

                

            # Find the smallest position where a new left cut is possible.

            while curr <= n and not dp[curr - 1]:

                curr += 1

            

            # If this subarray is of minimum size, this cut is possible.

            if curr <= i - k + 1:

                dp[i] = True

                

        return dp[-1]

    

    # Binary search the error.

    left, right = 0, photos[-1] - photos[1]

    ans = right

    

    while left <= right:

        mid = (left + right) // 2

        error = mid

        

        # If this error is possible, we can try for smaller error.

        if check(error):

            right = mid - 1

            ans = mid

        else:

            left = mid + 1

            

    return ans

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:

Output Format:

Note:

Constraints:

Top Samsung Research Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Samsung Research Software Developer