Last Updated: 24 Nov, 2020
Minimize the maximum difference between adjacent elements in an array
Easy
Asked in companies
You are given a non-decreasing array and an integer K. You need to remove exactly K integers from the given array such that the maximum difference between adjacent elements is minimum.
For example:
If the given array is: [2 6 7 7 10] and K = 2. We need to remove A[0] = 2 and A[4] = 10, then the resultant array would become [6 7 7], where the difference between adjacent pairs are {1, 0}. Thus our answer would be 1. You can see that there would not be any better answer than 1 for this array
Input Format:
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test case contains two space-separated integers N and K representing the length of the array and the number of integers to be removed.
The second line of each test case contains N space-separated integers denoting the elements of the given array.
Output Format:
For each test case, print the maximum difference between adjacent elements is minimum after K integers are removed, in a separate line.
Constraints:
1 ≤ T ≤ 100
3 ≤ N ≤ 1000
1 ≤ Ai ≤ 10^6
0 ≤ K ≤ N - 2
Time Limit : 1 sec
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Approaches
- Generate all the possible subsets of size N - K.
- This is because in the final array only N - K elements would remain.
- This can be done by doing Complete Search.
- Now take the maximum difference between adjacent elements.
- Take the minimum of all these subsets and return it as the answer.
- It can be noted that removing elements from the middle of the array would only maximise the final answer.
- For example: If the given array is: [arr1 arr2 … arrX-1 arrX arrX+1 ... arrN]. Possible answers can be: {arr2 - arr1, arr3 - arr2, …, arrX - arrX-1, arrX+1 - arrX, ... } and if we remove arrX, the possible answers becomes: {arr2 - arr1, arr3 - arr2, …, arrX+1 - arrX-1, ... }. Since the given array is non decreasing, the later answer would only maximise the final answer.
- This would mean that we should remove total K elements from the starting and the ending of the given array.
- That means we should take contiguous N - K elements in the final array.
- So we iterate over all the N - K possible subarrays, find the maximum adjacent difference between the elements and finally take the minimum of all and return it.
- Here, we will create a difference array, which will be an array of differences of adjacent elements of the initial array.
- To find the answer, we just have to find the minimum element of the maximum values present in all subarrays of size N - K - 1.
- This can be easily done by Sliding Window Minimum with a fixed subarray size.
- To do this, we maintain a deque of indices. The deque is made such that it is non increasing at any point.
- For finding the maximum value for any subarray, we just take the value at the front of the deque.
Similar problems