Minimum Removals

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.

If we draw the recursion tree for the recurrence relation of approach 1, we can observe that there are a lot of overlapping subproblems. There are only N^2 distinct recursive calls.

Lets understand this by an example, consider ARR = [1, 4, 8, 9]

The recursion tree for array will be :

As we can clearly see in the recursion tree that [4, 8] will be calculated twice.

Since the problem has overlapping subproblems, we can solve it more efficiently using memoization.

The algorithm is similar to the previous approach with some additions. 

We initialise a 2-D vector memo with -1. Now, memo[i][j] will store the minimum number of elements that should be removed such that the difference between the maximum element and minimum element of the array starting from index i and ending at j is less than or equal to K.

Before calling the function for any valid (i, j), we will check whether we already have a solution corresponding to the (i, j) present in memo. 

1. If we already have a solution corresponding to (i, j), we return the solution.
2. Else call the recursive function for (i+1, j) and (i, j-1) and store the minimum of them + 1 in memo[i][j] and return it..

Initially, we were breaking the large problem into small subproblems but now, let us look at it differently. The idea is to solve the small problem first and then reach the final answer. Thus we will be using a bottom-up approach now. 

Here is the algorithm:

1. We will initialise a 2-D matrix dp filled with 0. dp[i][j] will store the minimum number of elements that should be removed such that the difference between the maximum element and minimum element of the array starting from index i and ending at j is less than or equal to K.
2. Now we iterate over the matrix diagonally for i < j:
   1. If ARR[j] - ARR[i] <= K.
      1. dp[i][j] = 0. Since our condition is satisfied we don’t need to remove any element from the array.
   2. Else
      1. dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1.
3. Finally, return dp[0][N - 1].

In this approach we will find the ending index(j) for each starting index(i) for which arr[j] - arr[i] <= K. The number of elements to be removed is N - (j - i + 1). We will maintain the minimum of it for each starting index from 0 to N - 1 and return it as the final result.

We will use binary search to find j (end index) for each i (starting index). It will reduce the time complexity to log(N) for each i.