Minimize the maximum difference between adjacent elements in an array

PROBLEM STATEMENT

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.

Approach 1

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.

Try Problem

Approach 2

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.

Try Problem

Approach 3

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.

Try Problem