Minimum Removals

Moderate
0/80
Average time to solve is 10m
23 upvotes
Asked in companies
HCL TechnologiesDeutsche BankPayPal

Problem statement

You’re given an array ‘ARR’ of size N and an integer K. Your task is to determine the minimum number of elements that should be removed from the array such that the difference between the maximum and the minimum element in the remaining array is less than or equal to K.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains two space-separated integers N and K, where N is the size of the array and K is an integer such that the difference between the maximum and minimum element in the remaining array is less than or equal to K.

The second line of each test case contains N space-separated integers, denoting the array elements.
Output Format: 
For every test case, print a single line containing a single integer denoting the minimum number of elements that should be removed from the array, such that that the difference between the maximum and minimum element in the remaining array is less than or equal to K.

The output of each test case will be printed 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 <= 5
1 <=  N <= 10 ^ 5
-10 ^ 9 <= ARR[i] <= 10 ^ 9

Time limit: 1 sec
Sample Input 1:
1
5 5
1 6 4 3 7
Sample Output 1:
1
Explanation of Sample Input 1:
After removing only one element, i.e., 7, the maximum element and the minimum element in the remaining array are 6 and 1, respectively. The difference between them is 5, which is less than or equal to K. We can also remove 1 from the array. The difference between the maximum and minimum element in the remaining array will be 7 - 4 = 3, which is also less than or equal to K.
Sample Input 2:
1
6 4
5 6 8 10 9 7
Sample Output 2:
1
Explanation of Sample Input 2:
After removing only one element, i.e., 5, the maximum element and the minimum element in the remaining array are 10 and 6. The difference between them is 4, which is less than or equal to K. We can also remove 10 from the array. The difference between the maximum and minimum element in the remaining array will be 9 - 5 = 4, which is also less than or equal to K.
Hint

Check for all possible sub-arrays such that the difference between the maximum and the minimum element in the sub-array is less than or equal to K.

Approaches (2)
Brute Force

We will first sort the given array. Then we will start traversing the array using two variables, say ‘i’ and ‘j,’ using a nested loop, where j will be used to fix the maximum element, and i will be used to fix the minimum element and check if arr[j] - arr[i] <= K.

 

Algorithm:

 

  1. Sort the given array in increasing order.
  2. Make an integer variable “answer” = N to store the minimum number of elements that need to be removed from the array.
  3. Run a loop(loop variable ‘i’) from 0 till N - 1 to fix the minimum element in the array.
    1. Run a nested loop(loop variable ‘j’) from i till N -1 to fix the maximum element in the array.
    2. If arr[j] - arr[i] <= K, then update answer = min(answer, N - (j - i + 1) ), because we will be removing all the elements from the array except those elements which are present at index i to j.
  4. Return answer.
Time Complexity

O(N ^ 2), where N is the number of elements in the array.

 

We are running a loop from 0 till N - 1 to fix the minimum element and another loop from i till N - 1 to fix the maximum element. Hence it will take O(N ^ 2) time, and we are also sorting our array of size N, which will take O(N * log(N)). Hence, the final time complexity will be O(N ^ 2) + O(N * log(N)) = O(N ^ 2)

Space Complexity

O(1).

 

As we are using constant memory space.

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