Find minimum removals required in an array to satisfy given constraints
Given an integer array, trim it such that its maximum element becomes less than twice the minimum, return the minimum number of removals required for the conversion.
For example,
Output: The minimum number of removals is 4
The trimmed array is [7, 5, 9] where 9 < 2 × 5.
Input: [4, 2, 6, 4, 9]
Output: The minimum number of removals is 3
The trimmed array is [6, 4] where 6 < 2 × 4.
The idea is simple and effective – instead of removing elements from the array, view the problem as finding the largest subarray whose maximum element is less than twice the minimum.
Traverse the array from left to right and consider each element a starting point of a subarray. Then, with the starting index of the subarray fixed, greedily choose its other end as much away from it as possible. We can do this by expanding the subarray towards the right, one element at a time, provided that the newly added element satisfies the given condition. Do this for all subarrays to find the maximum size subarray. The minimum number of removals needed will be the difference between the array’s size and the maximum size subarray length.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> #include <algorithm> using namespace std; int findMin(int arr[], int n) { // Stores the length of the maximum size subarray int max_range = 0; // To keep track of the minimum and the maximum elements in a subarray int min, max; // Traverse the array and consider each element as a starting point of a subarray for (int i = 0; i < n && n - i > max_range; i++) { // Reset the minimum and the maximum elements // (from the previous iteration of the loop) min = max = arr[i]; /* Subarray invariant: max < 2×min */ // Find the maximum size subarray `arr[i…j]` that satisfies the // above invariant for (int j = i; j < n; j++) { // Find the minimum and the maximum elements in the current subarray. // We must do this in constant time. min = std::min(min, arr[j]); max = std::max(max, arr[j]); // Discard the subarray if the invariant is violated if (2 * min <= max) { break; } // Update `max_range` when a bigger subarray is found max_range = std::max(max_range, j - i + 1); } } // Return array size - length of the maximum size subarray return n - max_range; } int main() { int arr[] = { 4, 6, 1, 7, 5, 9, 2 }; int n = end(arr) - begin(arr); cout << "The minimum number of removals is " << findMin(arr, n); return 0; } |
Output:
The minimum number of removals is 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class Main { public static int findMin(int[] arr) { // Stores the length of the maximum size subarray int max_range = 0; // To keep track of the minimum and the maximum elements in a subarray int min, max; // Traverse the array and consider each element as a starting point // of a subarray for (int i = 0; i < arr.length && arr.length - i > max_range; i++) { // Reset the minimum and the maximum elements // (from the previous iteration of the loop) min = max = arr[i]; /* Subarray invariant: max < 2×min */ // Find the maximum size subarray `arr[i…j]` that satisfies // the above invariant for (int j = i; j < arr.length; j++) { // Find the minimum and the maximum elements in the current subarray. // We must do this in constant time. min = Integer.min(min, arr[j]); max = Integer.max(max, arr[j]); // Discard the subarray if the invariant is violated if (2 * min <= max) { break; } // Update `max_range` when a bigger subarray is found max_range = Integer.max(max_range, j - i + 1); } } // Return array size - length of the maximum size subarray return arr.length - max_range; } public static void main(String[] args) { int[] arr = { 4, 6, 1, 7, 5, 9, 2 }; System.out.println("The minimum number of removals is " + findMin(arr)); } } |
Output:
The minimum number of removals is 4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
def findMin(arr): # Stores the length of the maximum size subarray max_range = 0 # Traverse the array and consider each element as a starting point of a subarray for i in range(len(arr)): ''' Subarray invariant: max < 2×min ''' # To keep track of the minimum and the maximum elements in a subarray min_arr = max_arr = arr[i] # Find the maximum size subarray `arr[i…j]` that satisfies # the above invariant for j in range(i, len(arr)): # Find the minimum and the maximum elements in the current subarray. # We must do this in constant time. min_arr = min(min_arr, arr[j]) max_arr = max(max_arr, arr[j]) # Discard the subarray if the invariant is violated if 2 * min_arr <= max_arr: break # Update `max_range` when a bigger subarray is found max_range = max(max_range, j - i + 1) # Return array size - length of the maximum size subarray return len(arr) - max_range if __name__ == '__main__': arr = [4, 6, 1, 7, 5, 9, 2] print("The minimum number of removals is", findMin(arr)) |
Output:
The minimum number of removals is 4
The time complexity of the above solution is O(n2) and doesn’t require any extra space, where n is the size of the input.
Exercise: Modify the solution to print the trimmed array as well.
Truncate an integer array such that `2×min` becomes more than `max`
Find the minimum and maximum element in an array using Divide and Conquer
Find the minimum and maximum element in an array using minimum comparisons
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)