Find elements which need to be removed from an array such that 2*min>max

Question

Consider the following problem:

An array of integers is given. Your goal is to trim the array such that 2*min > max, where min and max are the minimum and maximum elements of the array. You can remove elements either from start or from end of the array if above condition does not meet. The number of removals should be minimized.

For example if the array is

a, b, c, d, e, f

where c is the minimum and e is the maximum, then if 2*c > e is true, we are done. If not, we could remove either from the start (i.e. a,b,c) or from the end (i.e. e, f) such that new min or max would satisfy the condition and removals should be minimum.

I have an O(n²) algorithm for this problem. Can this be solved in time O(n log n)?

Answer 1

Note that the problem is to find the largest subarray that fulfills the condition. Realize that if the condition holds for an interval of indices, it holds also for all the intervals included in it. So if we fix one border, we can greedily choose the other border as much away from it as possible.

It's possible to solve this in linear time:

Define r_i as the rightmost possible right boundary if you choose element i as the left boundary. We can show that r is monotonous in i, so we can maintain two pointers to i and r_i and increment r_i as much as possible every time after we increment i by one. Both pointers are incremented a total of O(n) times and we can maintain the range minima / maxima in O(log n) per increment using a heap or binary search tree of the values in the range.

Using a monotonic queue we can maintain the extrema in O(1) and get a total runtime of O(n). Another C++ implementation of the queue can be found here, for example.

---

Another somewhat less elegant way would be to use a RMQ data structure. It let's you query the min/max in a range in O(1) after O(n log n) preprocessing (O(n) preprocessing is also possible, but complicated and unnecessary here, since the rest of the algorithm is not linear time).

Now fix the left border (there are n possibilities). Use binary search to find the rightmost right boundary which still fulfills the condition (you can check in O(1) whether it does).

This works because the predicate "range fulfills the condition" is monotonous with regard to inclusion (if a range fulfills it, all ranges included in it also fulfill it).

Answer 2

Can you change the order of elements in the array? If so, you can do the following steps:

1. Sort the array with for example the quicksort or whatever best fits your requirements -> O(n lg n)
2. Take the first key k = 2*input[0] -> O(1)
3. Use the binary search algorithm to find the index of the key k in the array -> O(lg n)
4. If the found index is greater than half the lenght of the input array remove the last part of the array, otherwise remove the first part. -> O(1)

In this case the complexity is the sum of O(n ln n) + O(1) + O(lg n) + O(1) => O(n lg n)