Last Updated: 23 Nov, 2021
Minimum Removals
Moderate
Asked in company
On your 20th birthday, one of your friends gifted you an array 'A' of 'N' positive integers. But you don't like an array having a large difference among numbers. To reduce the difference, you are going to perform the following operations on the array.
Remove an element from the start of the array.
Remove an element from the end of the array.
In one operation, you can remove only one element, either from the start or from the end. Your task is to find the minimum number of operations, after which array 'A' holds the following property -
2 * min > max
Where 'min' is the minimum element of the array, and 'max' is the maximum element of the array, calculated each time for the updated array.
You can perform any operations of your choice, but minimize the number of operations and return it.
Input Format:
The first line contains an integer 'T', denoting the number of tests.
For each Test :
The first line contains an integer 'N', denoting the length of the array 'A'.
The second line contains an array 'A' of length 'N'.
Output Format:
For each test, print an integer, denoting the minimum number of operations required such that the given condition holds true.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= 'T' <= 5
1 <= 'N' <= 10^5
1 <= A[i] < 10^9 i ∈ (1,N)
Time Limit: 1 sec
Approaches
Approach: Implement a recursive function that accepts the index range to be processed. Initially, the function is called for the entire array, i.e., L= 1 and R = N.
In each recursion call, find the minimum and maximum elements in the array, and if condition (2*min > max) holds, return 0, denoting that 0 removals are needed for range [L, R]. Otherwise, the answer for this call will be [1 + minimum among recursion(L+1, R) and recursion(L, R-1)].
Algorithm:
- Implement a function that takes three parameters: array ‘A’, left endpoint ‘L’, right endpoint ‘R’.
- Let ‘min’ be the minimum element, and ‘max’ be the maximum element in array ‘A’ for index range [L, R].
- If (2*min > max) holds true, return 0.
- Otherwise, return [1 + minimum of recursion(A, L+1, R) and recursion(A, L, R-1) ].
- Call the above recursion from the main function for range L=1 and R=N, and return the answer.
Approach: In brute force approach, the same subproblems are getting solved multiple times. For example, recursion(L+1, R-1) will be called from recursion(L, R-1) and recursion(L+1, R) both.
This thing can be optimized using dynamic programming. A dp of size N*N is made where dp[i][j] contains the same result as recursion(i, j), but no pair (i, j) will be calculated more than once.
Algorithm:
- Create a dp of size N*N.
- Iterate a for loop k = 0 to N-1, denoting the distance between endpoints ‘L’ and ‘R’.
- Initialize L = 1 and R = k+1.
- While R is less than or equal to N:
- Let ‘min’ be the minimum element and ‘max’ be the maximum element in array ‘A’ for index range [L, R].
- If (2*min > max) holds true, dp[L][R] = 0.
- Else, dp[L][R] = 1 + min(dp[L + 1][R], dp[L][R - 1]).
- Increment L and R by 1.
- Let ‘min’ be the minimum element and ‘max’ be the maximum element in array ‘A’ for index range [L, R].
- This iteration fills all pairs [L, R] where, R - L + 1 = k.
- We need a final answer for the entire array, so return dp[1][N].
Approach: Let’s forget about which elements need to be removed. Ultimately, we need the longest subarray that satisfies the given condition.
Run two nested loops to fix the starting and ending points of subarrays and keep track of the minimum and maximum values. Among all the subarrays which satisfy the given condition, consider the length of the longest subarray. Let the longest length be ‘len’, our answer becomes [N - len].
Algorithm:
- Initialize ‘len’ with 0.
- Iterate a for loop L = 1 to N, denoting starting point of subarrays.
- Initialize ‘min’ with infinite and ‘max’ with 0.
- Iterate a for loop R = L to N, denoting ending point of subarrays.
- Update ‘min’ and ‘max’ with current element.
- If 2*min > max, maximize ‘len’ with current length.
- Else, break.
- Return (N - len).
Similar problems