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).