In O(n log k) time?

The brute force solution would be to iterate over every element, and then iterate over all elements within k distance of it, finding the maximum and minimum, and checking to make sure the maximum is less than 2x the minimum.

However, that would take O(nk) time. Is there a way to do this in O(n log k)?

I was thinking about maintaining a min heap and a max heap (as insert and delete operations have a runtime of O(log k)), but it seems like a lot of extra work (you would have to keep a hashtable of element positions in the heap in order to remove them).

Any ideas?

In O(n log k) time?

The input is the array of integers n, and some integer k. The output should be a boolean for whether or not the following condition holds for all elements: any two elements within k distance of this element cannot vary by a multiple of two (the maximum cannot be double the minimum).

The brute force solution would be to iterate over every element, and then iterate over all elements within k distance of it, finding the maximum and minimum, and checking to make sure the maximum is less than 2x the minimum.

However, that would take O(nk) time. Is there a way to do this in O(n log k)?

I was thinking about maintaining a min heap and a max heap (as insert and delete operations have a runtime of O(log k)), but it seems like a lot of extra work (you would have to keep a hashtable of element positions in the heap in order to remove them).

Any ideas?