Given an array of integers, 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,
The idea is straightforward and effective – instead of removing elements from the array, view the problem as finding the largest sub-array whose maximum element is less than twice the minimum.
The idea is to traverse the array from left to right and consider each element a starting point of a sub-array. Then, with the starting index of sub-array fixed, greedily choose its other end as much away from it as possible. This can be done by expanding the sub-array towards the right, one element at a time, provided that the newly added element satisfies the given condition. Do this for all sub-arrays to find the maximum size sub-array. The minimum number of removals needed will be the difference between the array’s size and the length of the maximum size sub-array.
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int findMin(int arr[], int n)
{
// Stores the length of the maximum size sub-array
int max_range = 0;
// To keep track of the min and max elements in a sub-array
int min, max;
// Traverse the array and consider each element as a starting point of a sub-array
for (int i = 0; i < n && n – i > max_range; i++)
{
// Reset the min and max elements (from previous iteration of loop)
min = max = arr[i];
/*
Sub-array invariant: max < 2*min
*/
// Find the maximum size sub-array `arr[i..j]` that satisfies the
// above invariant
for (int j = i; j < n; j++)
{
// Find the min and max elements in the current sub-array.
// We must do this in constant time.
min = std::min(min, arr[j]);
max = std::max(max, arr[j]);
// Discard the sub-array if the invariant is violated
if (2 * min <= max) {
break;
}
// Update max_range when a bigger sub-array is found
max_range = std::max(max_range, j – i + 1);
}
}
// Return size of the array – length of the maximum size sub-array
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 are “ << findMin(arr, n);
return 0;
}
|
Output:
The minimum number of removals are 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
|
class Main
{
public static int findMin(int[] arr)
{
// Stores the length of the maximum size sub-array
int max_range = 0;
// To keep track of the min and max elements in a sub-array
int min, max;
// Traverse the array and consider each element as a starting point
// of a sub-array
for (int i = 0; i < arr.length && arr.length – i > max_range; i++)
{
// Reset the min and max elements (from previous iteration of loop)
min = max = arr[i];
/*
Sub-array invariant: max < 2*min
*/
// Find the maximum size sub-array `arr[i..j]` that satisfies
// the above invariant
for (int j = i; j < arr.length; j++)
{
// Find the min and max elements in the current sub-array.
// We must do this in constant time.
min = Integer.min(min, arr[j]);
max = Integer.max(max, arr[j]);
// Discard the sub-array if the invariant is violated
if (2 * min <= max) {
break;
}
// Update max_range when a bigger sub-array is found
max_range = Integer.max(max_range, j – i + 1);
}
}
// Return size of the array – length of the maximum size sub-array
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 are “ + findMin(arr));
}
}
|
Output:
The minimum number of removals are 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
|
def findMin(arr):
# Stores the length of the maximum size sub-array
max_range = 0
# Traverse the array and consider each element as a starting point of a sub-array
for i in range(len(arr)):
“””
Sub-array invariant: max < 2*min
“””
# To keep track of the min and max elements in a sub-array
min_arr = max_arr = arr[i]
# Find the maximum size sub-array `arr[i..j]` that satisfies
# the above invariant
for j in range(i, len(arr)):
# Find the min and max elements in the current sub-array.
# We must do this in constant time.
min_arr = min(min_arr, arr[j])
max_arr = max(max_arr, arr[j])
# Discard the sub-array if the invariant is violated
if 2 * min_arr <= max_arr:
break
# Update max_range when a bigger sub-array is found
max_range = max(max_range, j – i + 1)
# Return size of the array – length of the maximum size sub-array
return len(arr) – max_range
if __name__ == ‘__main__’:
arr = [4, 6, 1, 7, 5, 9, 2]
print(“The minimum number of removals are”, findMin(arr))
|
Output:
The minimum number of removals are 4
Download Run Code
Output:
The minimum number of removals are 4
Download Run Code
Output:
The minimum number of removals are 4
Download Run Code
Output:
The minimum number of removals are 4
The time complexity of the above solution is O(n2) and requires O(1) extra space.
Exercise: Modify the solution to print the trimmed array as well.