Minimize the maximum difference between adjacent elements in an array

Easy

0/40

Average time to solve is 15m

65 upvotes

Asked in companies

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

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

Sample Output 1:

1
0
3

Explanation of Input 1:

The first test case has already been explained in the problem statement.
For the second test case, the given array is: [4 6 6] and K = 1. We remove A[0] = 4, then the resultant array would become [6 6]. So the answer would be 0.
For the third test case, the given array is: [3 6 6 7] and K = 0. We cannot remove any number. The array remains the same. So the answer becomes 3.

Sample Input 2:

3
9 6
3 3 4 6 7 10 10 12 15 
4 0
1 1 3 3 
9 7
1 1 2 5 7 10 13 16 17

Sample Output 2

1
2
0

Hint 1

Hint 2

Hint 3

Generate all possible solutions and take the minimum

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

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.

Time Complexity

O(2^N * (N - K)) where N is the size of the given array and we need to remove K elements from the given array.

Since we are generating all the subsets it would take O(2^N) and then traversing each subset which would take O(N - K).

Space Complexity

O(1),

In the worst case, only constant extra space is required.

(100% EXP penalty)

Minimize the maximum difference between adjacent elements in an array

Console