Find the elements you want to remove from the array, so 2 * min> max

Question

Consider the following task:

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

For example, if an array

a, b, c, d, e, f 

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

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. Understand that if a condition is satisfied for an index interval, it is also satisfied for all intervals included in it. Therefore, if we correct one border, we can eagerly choose another border as far as possible from it.

This can be solved in linear time:

Define r _i as the rightmost edge if you select the i element as the left border. We can show that r is monotonic in i, so we can maintain two pointers to i and r _i and increase r _i as much as possible each time after we increase i by one. Both pointers increase in total O (n) times, and we can maintain the minimum / maximum values ​​of the range in O (log n) for each increment, using a heap or binary search tree for values ​​in the range.

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

---

Another less elegant way would be to use the RMQ data structure . This allows you to request min / max in a range in O (1) after O (n log n) preprocessing (O (n) preprocessing is 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 a binary search to find the far right edge that still satisfies the condition (you can check O (1) if that does).

This works because the predicate "range satisfies the condition" is monotonic with respect to inclusion (if the range satisfies it, all ranges included in it also fulfill it).

Answer 2

Can you reorder the elements in an array? If so, you can take the following steps:

• Sorting an array using, for example, quicksort or any other suitable option your requirements → O (n lg n)
• Take the first key k = 2 * input [0] → O (1)
• Use the binary search algorithm to find the index of the key k in the array → O (log n)
• If the found index is more than half the length of the input array, delete the last part of the array, otherwise delete the first part. → O (1)

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