# Minimum removals from array to make max – min <= K

Given N integers and K, find the minimum number of elements that should be removed such that Amax-Amin<=K. After removal of elements, Amax and Amin is considered among the remaining elements.
Examples:

```Input : a[] = {1, 3, 4, 9, 10, 11, 12, 17, 20}
k = 4
Output : 5
Explanation: Remove 1, 3, 4 from beginning
and 17, 20 from the end.

Input : a[] = {1, 5, 6, 2, 8}  K=2
Output : 3
Explanation: There are multiple ways to
remove elements in this case.
One among them is to remove 5, 6, 8.
The other is to remove 1, 2, 5
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: Sort the given elements. Using greedy approach, the best way is to remove the minimum element or the maximum element and then check if Amax-Amin <= K. There are various combinations of removals that have to be considered. We write a recurrence relation to try every possible combination. There will be two possible ways of removal, either we remove the minimum or we remove the maximum. Let(i…j) be the index of elements left after removal of elements. Initially, we start with i=0 and j=n-1 and the number of elements removed is 0 at the beginning. We only remove an element if a[j]-a[i]>k, the two possible ways of removal are (i+1…j) or (i…j-1). The minimum of the two is considered.

Let DPi, j be the number of elements that need to be removed so that after removal a[j]-a[i]<=k.

Recurrence relation for sorted array:

`DPi, j = 1+ (min(countRemovals(i+1, j), countRemovals(i, j-1))`

Below is the implementation of the above idea:

## C++

 `// CPP program to find minimum removals ` `// to make max-min <= K ` `#include ` `using` `namespace` `std; ` ` `  `#define MAX 100 ` `int` `dp[MAX][MAX]; ` ` `  `// function to check all possible combinations ` `// of removal and return the minimum one ` `int` `countRemovals(``int` `a[], ``int` `i, ``int` `j, ``int` `k) ` `{ ` `    ``// base case when all elements are removed ` `    ``if` `(i >= j) ` `        ``return` `0; ` ` `  `    ``// if condition is satisfied, no more ` `    ``// removals are required ` `    ``else` `if` `((a[j] - a[i]) <= k) ` `        ``return` `0; ` ` `  `    ``// if the state has already been visited ` `    ``else` `if` `(dp[i][j] != -1) ` `        ``return` `dp[i][j]; ` ` `  `    ``// when Amax-Amin>d ` `    ``else` `if` `((a[j] - a[i]) > k) { ` ` `  `        ``// minimum is taken of the removal ` `        ``// of minimum element or removal ` `        ``// of the maximum element ` `        ``dp[i][j] = 1 + min(countRemovals(a, i + 1, j, k), ` `                           ``countRemovals(a, i, j - 1, k)); ` `    ``} ` `    ``return` `dp[i][j]; ` `} ` ` `  `// To sort the array and return the answer ` `int` `removals(``int` `a[], ``int` `n, ``int` `k) ` `{ ` `    ``// sort the array ` `    ``sort(a, a + n); ` ` `  `    ``// fill all stated with -1 ` `    ``// when only one element ` `    ``memset``(dp, -1, ``sizeof``(dp)); ` `    ``if` `(n == 1) ` `        ``return` `0; ` `    ``else` `        ``return` `countRemovals(a, 0, n - 1, k); ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``int` `a[] = { 1, 3, 4, 9, 10, 11, 12, 17, 20 }; ` `    ``int` `n = ``sizeof``(a) / ``sizeof``(a[0]); ` `    ``int` `k = 4; ` `    ``cout << removals(a, n, k); ` `    ``return` `0; ` `} `

/div>

## Java

 `// Java program to find minimum removals ` `// to make max-min <= K ` `import` `java.util.Arrays; ` ` `  `class` `GFG ` `{ ` `    ``static` `int` `MAX=``100``; ` `    ``static` `int` `dp[][]=``new` `int``[MAX][MAX]; ` `     `  `    ``// function to check all possible combinations ` `    ``// of removal and return the minimum one ` `    ``static` `int` `countRemovals(``int` `a[], ``int` `i, ``int` `j, ``int` `k) ` `    ``{ ` `        ``// base case when all elements are removed ` `        ``if` `(i >= j) ` `            ``return` `0``; ` `     `  `        ``// if condition is satisfied, no more ` `        ``// removals are required ` `        ``else` `if` `((a[j] - a[i]) <= k) ` `            ``return` `0``; ` `     `  `        ``// if the state has already been visited ` `        ``else` `if` `(dp[i][j] != -``1``) ` `            ``return` `dp[i][j]; ` `     `  `        ``// when Amax-Amin>d ` `        ``else` `if` `((a[j] - a[i]) > k) { ` `     `  `            ``// minimum is taken of the removal ` `            ``// of minimum element or removal ` `            ``// of the maximum element ` `            ``dp[i][j] = ``1` `+ Math.min(countRemovals(a, i + ``1``, j, k), ` `                                    ``countRemovals(a, i, j - ``1``, k)); ` `        ``} ` `        ``return` `dp[i][j]; ` `    ``} ` `     `  `    ``// To sort the array and return the answer ` `    ``static` `int` `removals(``int` `a[], ``int` `n, ``int` `k) ` `    ``{ ` `        ``// sort the array ` `        ``Arrays.sort(a); ` `     `  `        ``// fill all stated with -1 ` `        ``// when only one element ` `        ``for``(``int``[] rows:dp) ` `        ``Arrays.fill(rows,-``1``); ` `        ``if` `(n == ``1``) ` `            ``return` `0``; ` `        ``else` `            ``return` `countRemovals(a, ``0``, n - ``1``, k); ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `a[] = { ``1``, ``3``, ``4``, ``9``, ``10``, ``11``, ``12``, ``17``, ``20` `}; ` `        ``int` `n = a.length; ` `        ``int` `k = ``4``; ` `        ``System.out.print(removals(a, n, k)); ` `    ``} ` `} ` ` `  `// This code is contributed by Anant Agarwal. `

## Python3

 `# Python program to find  ` `# minimum removals to ` `# make max-min <= K ` `MAX` `=` `100` `dp ``=` `[[``0` `for` `i ``in` `range``(``MAX``)]  ` `         ``for` `i ``in` `range``(``MAX``)] ` `for` `i ``in` `range``(``0``, ``MAX``) : ` `    ``for` `j ``in` `range``(``0``, ``MAX``) : ` `        ``dp[i][j] ``=` `-``1` ` `  `# function to check all  ` `# possible combinations ` `# of removal and return ` `# the minimum one ` `def` `countRemovals(a, i, j, k) : ` ` `  `    ``global` `dp ` `     `  `    ``# base case when all  ` `    ``# elements are removed ` `    ``if` `(i >``=` `j) : ` `        ``return` `0` ` `  `    ``# if condition is satisfied,  ` `    ``# no more removals are required ` `    ``elif` `((a[j] ``-` `a[i]) <``=` `k) : ` `        ``return` `0` ` `  `    ``# if the state has  ` `    ``# already been visited ` `    ``elif` `(dp[i][j] !``=` `-``1``) : ` `        ``return` `dp[i][j] ` ` `  `    ``# when Amax-Amin>d ` `    ``elif` `((a[j] ``-` `a[i]) > k) : ` ` `  `        ``# minimum is taken of  ` `        ``# the removal of minimum ` `        ``# element or removal of  ` `        ``# the maximum element ` `        ``dp[i][j] ``=` `1` `+` `min``(countRemovals(a, i ``+` `1``,  ` `                                         ``j, k), ` `                           ``countRemovals(a, i,  ` `                                         ``j ``-` `1``, k)) ` `    ``return` `dp[i][j] ` ` `  `# To sort the array  ` `# and return the answer ` `def` `removals(a, n, k) : ` ` `  `    ``# sort the array ` `    ``a.sort() ` ` `  `    ``# fill all stated  ` `    ``# with -1 when only ` `    ``# one element ` `    ``if` `(n ``=``=` `1``) : ` `        ``return` `0` `    ``else` `: ` `        ``return` `countRemovals(a, ``0``,  ` `                             ``n ``-` `1``, k) ` ` `  `# Driver Code ` `a ``=` `[``1``, ``3``, ``4``, ``9``, ``10``,  ` `     ``11``, ``12``, ``17``, ``20``] ` `n ``=` `len``(a) ` `k ``=` `4` `print` `(removals(a, n, k)) ` ` `  `# This code is contributed by  ` `# Manish Shaw(manishshaw1) `

## C#

 `// C# program to find minimum  ` `// removals to make max-min <= K ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``static` `int` `MAX = 100; ` `    ``static` `int` `[,]dp = ``new` `int``[MAX, MAX]; ` `     `  `    ``// function to check all  ` `    ``// possible combinations ` `    ``// of removal and return ` `    ``// the minimum one ` `    ``static` `int` `countRemovals(``int` `[]a, ``int` `i, ` `                             ``int` `j, ``int` `k) ` `    ``{ ` `        ``// base case when all ` `        ``// elements are removed ` `        ``if` `(i >= j) ` `            ``return` `0; ` `     `  `        ``// if condition is satisfied,  ` `        ``// no more removals are required ` `        ``else` `if` `((a[j] - a[i]) <= k) ` `            ``return` `0; ` `     `  `        ``// if the state has ` `        ``// already been visited ` `        ``else` `if` `(dp[i, j] != -1) ` `            ``return` `dp[i, j]; ` `     `  `        ``// when Amax-Amin>d ` `        ``else` `if` `((a[j] - a[i]) > k) ` `        ``{ ` `     `  `            ``// minimum is taken of the  ` `            ``// removal of minimum element  ` `            ``// or removal of the maximum  ` `            ``// element ` `            ``dp[i, j] = 1 + Math.Min(countRemovals(a, i + 1,  ` `                                                  ``j, k), ` `                                    ``countRemovals(a, i,  ` `                                                  ``j - 1, k)); ` `        ``} ` `        ``return` `dp[i, j]; ` `    ``} ` `     `  `    ``// To sort the array and ` `    ``// return the answer ` `    ``static` `int` `removals(``int` `[]a,  ` `                        ``int` `n, ``int` `k) ` `    ``{ ` `        ``// sort the array ` `        ``Array.Sort(a); ` `     `  `        ``// fill all stated with -1 ` `        ``// when only one element ` `        ``for``(``int` `i = 0; i < MAX; i++)  ` `        ``{ ` `            ``for``(``int` `j = 0; j < MAX; j++) ` `                ``dp[i, j] = -1; ` `        ``} ` `        ``if` `(n == 1) ` `            ``return` `0; ` `        ``else` `            ``return` `countRemovals(a, 0,  ` `                                 ``n - 1, k); ` `    ``} ` `     `  `    ``// Driver code ` `    ``static` `void` `Main()  ` `    ``{ ` `        ``int` `[]a = ``new` `int``[]{ 1, 3, 4, 9, 10,  ` `                             ``11, 12, 17, 20 }; ` `        ``int` `n = a.Length; ` `        ``int` `k = 4; ` `        ``Console.Write(removals(a, n, k)); ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// ManishShaw(manishshaw1) `

## PHP

 `= ``\$j``) ` `        ``return` `0; ` ` `  `    ``// if condition is satisfied,  ` `    ``// no more removals are required ` `    ``else` `if` `((``\$a``[``\$j``] - ``\$a``[``\$i``]) <= ``\$k``) ` `        ``return` `0; ` ` `  `    ``// if the state has  ` `    ``// already been visited ` `    ``else` `if` `(``\$dp``[``\$i``][``\$j``] != -1) ` `        ``return` `\$dp``[``\$i``][``\$j``]; ` ` `  `    ``// when Amax-Amin>d ` `    ``else` `if` `((``\$a``[``\$j``] - ``\$a``[``\$i``]) > ``\$k``)  ` `    ``{ ` ` `  `        ``// minimum is taken of  ` `        ``// the removal of minimum ` `        ``// element or removal of  ` `        ``// the maximum element ` `        ``\$dp``[``\$i``][``\$j``] = 1 + min(countRemovals(``\$a``, ``\$i` `+ 1,  ` `                                                ``\$j``, ``\$k``), ` `                              ``countRemovals(``\$a``, ``\$i``,  ` `                                            ``\$j` `- 1, ``\$k``)); ` `    ``} ` `    ``return` `\$dp``[``\$i``][``\$j``]; ` `} ` ` `  `// To sort the array  ` `// and return the answer ` `function` `removals(``\$a``, ``\$n``, ``\$k``) ` `{ ` `    ``// sort the array ` `    ``sort(``\$a``); ` ` `  `    ``// fill all stated with -1 ` `    ``// when only one element ` `    ``if` `(``\$n` `== 1) ` `        ``return` `0; ` `    ``else` `        ``return` `countRemovals(``\$a``, 0,  ` `                             ``\$n` `- 1, ``\$k``); ` `} ` ` `  `// Driver Code ` `\$a` `= ``array``(1, 3, 4, 9, 10,  ` `           ``11, 12, 17, 20); ` `\$n` `= ``count``(``\$a``); ` `\$k` `= 4; ` `echo` `(removals(``\$a``, ``\$n``, ``\$k``)); ` ` `  `// This code is contributed by  ` `// Manish Shaw(manishshaw1) ` `?> `

Output:

```5
```

Time Complexity :O(n2)
Auxiliary Space: O(n2)

This article is attributed to GeeksforGeeks.org

code

load comments