The easiest solution is:
- Sort the list first (Complexity O(nlogn)
- With a moving window, find the largest acceptable window. (Complexity O(n))
Complexity: O(nlogn).
More details about step2:
Let low keep track of the lowest element and high the highest element.
Initialization: Set low to the first element. Do a binary search for 4*x[low], and that is your high location. Set maxWindow=high-low+1.
At every step: Increment high by 1, and increment low such that x[low]>=x[high]. Calculate number of elements = high-low+1, and update maxWindow accordingly.