Minimum Removals

Moderate
0/80
Average time to solve is 15m
28 upvotes
Asked in companies
AdobeRubrik, Inc.Microsoft

Problem statement

You have been given an array/list "ARR" consisting of 'N' integers. You have also given an integer 'K'.

Your task is to find the minimum number of elements that should be removed from "ARR" (possibly zero) such that the difference between the maximum element and the minimum element of the remaining "ARR" is less than or equal to 'K', i.e. ARRmax - ARRmin <= K.

Note :

1. "ARR" can contain duplicates.

For Example :

Input: 'N' = 4 , "ARR" =  [5, 10 , 2] and 'K' = 3.
Output: 1

Explanation : Currently, the difference between the maximum and minimum element in the array is 10 - 2 = 8, which is greater than K (3). 
So, we need to remove some elements. The optimal way to get our result is to remove 10. After removing 10, the difference between maximum and minimum is 5 - 2 = 3, which is less than or equal to K.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two single-space separated integers ‘N’ and ‘K’, respectively.

The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array/list.
Output Format : 
Print the minimum number of elements that should be removed such that the difference between the maximum element and the minimum element of the remaining array is less than or equal to K.

Print the output of each test case in a separate line.

Note: You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 5000
0 <= K <= 10^5
-10^5 <= ARR[i] <=10^5

Where 'N' denotes the number of elements in the given array/list, 'K' is the given integer and ARR[i] denotes the i-th element of the given array/list.

Time Limit : 1 second
Sample Input 1 :
1
3 1
2 -7 -11
Sample Output 1:
2

Explanation for Sample 1:

Currently, the difference between the maximum and minimum element in the array is 2 - (-11) = 13 which is greater than K (1). So, we need to remove some elements. The optimal way to get our result is to remove any 2 elements from the array because if we remove any one element, the difference between maximum and minimum will not become less than K (1). 

After removing any two elements the difference between maximum and minimum element becomes 0 which is less than or equal to K (1).
Sample Input 2 :
2
4 0
2 6 -5 2
4 4
1 2 5 3
Sample Output 2 :
2
0
Hint

Can you come up with a recurrence relation?

Approaches (4)
Recursion

The key observation here is that the best way to remove an element from the array is to remove the maximum or minimum element from the array. There are two possible ways of removal, either we remove the minimum element or the maximum element.

Now, the idea is to use recursion to reduce the big problem into several small subproblems. 

 

Here is the algorithm :

  1. We sort the array in ascending order.
  2. We will call a minRemovals function that returns us the minimum number of elements that should be removed such that the difference between the maximum element and minimum element of the remaining array is less than or equal to K. The minRemovals function will work as follows (here i and j denotes starting and ending index of ARR):
    1. If i >= j
      1. Return 0.
    2. If ARR[j] - ARR[i] <= K
      1. Return 0.
    3. Finally, we do a recursive call for (i + 1, j) and (i, j - 1) and 1 + minimum of them will be our answer.
Time Complexity

O(2 ^ N), where ‘N’ denotes the number of elements in an array.

 

Since we are sorting the array, the time complexity for sorting will be O(N * log(N)). Also, in the worst case at every step, we are making two recursive calls and the maximum depth of the recursion tree can go up to N. Hence, the overall time complexity is O(2 ^ N).

Space Complexity

O(N), where ‘N’ denotes the number of elements in an array.

 

In the worst case, extra space is used by the recursion stack which can go up to a maximum depth of N. Hence the space complexity is O(N). 

Code Solution
(100% EXP penalty)
Minimum Removals
Full screen
Console