Minimize the maximum difference between adjacent elements in an array
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.

Question

Minimize the maximum difference between adjacent elements in an array

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.

Accepted Answer

The first observation I had was what would I do if the first and last elements were not fixed. I was not able to solve this question completely, hence I used brute force approach(provided in above link) to pass some of the test cases.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1),

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

Time Complexity: OtherExplanation:

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

Accepted Answer

Optimal Solution

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.

Space Complexity: O(1)Explanation:

O(1),

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

Time Complexity: OtherExplanation:

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

Since we would be traversing over each subarray of size (N - K) for each subarray starting from index 0 to K.

Accepted Answer

Efficient Solution

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.

Space Complexity: O(n)Explanation:

O(N) where N is the size of the given array.

Since we are making a difference array of size N - 1.

Time Complexity: O(n)Explanation:

O(N) where N is the size of the given array.

This is because we are traversing through the given array twice.

Java (SE 1.8)

/*
        Time Complexity - O(N)
        Space Complexity - O(N)

        Where N is the size of the given array.
*/


import java.util.Deque;
import java.util.LinkedList;

public class Solution {
	
	public static int findMinAnswer(int arr[], int n, int k)
	{
		Deque d = new LinkedList<>();

		for (int i = 0; i < k; ++i)
		{
			while(!d.isEmpty() && arr[d.getLast()] <= arr[i])
			{
				d.removeLast();
			}

			d.add(i);
		}

		int minAnswer = arr[d.getFirst()];

		for (int i = k; i < n; ++i)
		{
			if(!d.isEmpty() && d.getFirst() == i - k)
			{
				d.removeFirst();
			}

			while(!d.isEmpty() && arr[d.getLast()] <= arr[i])
			{
				d.removeLast();
			}

			d.add(i);

			minAnswer = Math.min(minAnswer, arr[d.getFirst()]);
		}

		return minAnswer;
	}

	public static int maxAdjDifference(int arr[], int n, int k)
	{
		int diff[] = new int[n-1];

		for (int i = 0; i < n - 1; ++i)
		{
			diff[i] = arr[i + 1] - arr[i];
		}

		return findMinAnswer(diff, n - 1, n - k - 1);
	}

}

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:

Input Format:

Output Format:

Constraints:

Note:

Top Urban Company Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Urban Company Software Developer