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?

  • $\begingroup$ Thank you! The input is an array of size n, and the output is a boolean yes or no. We want to check the following for all elements in the array, but suppose we are looking specifically at element of index i. We want to check that, for some distance k, no two elements within (i - k)...(i + k) vary by a multiple of 2. In other words, the minimum value around i within distance k can't be less than half of the maximum value around i within distance k. $\endgroup$ – Jake Hall Feb 1 '17 at 4:32
  • 1
    $\begingroup$ Rather than adding a comment, please edit the question to improve it. We want the question to stand on its own so people don't have to read comments -- and we want the question to read well for someone who encounters it for the first time. (This is part of our site format -- we want to build up an archive of high-quality questions and answers that might be useful to others in the future.) Also, where does k come from? Is it a fixed constant? Is it part of the input? $\endgroup$ – D.W. Feb 1 '17 at 5:59
  • $\begingroup$ Yes, k is part of the input. $\endgroup$ – Jake Hall Feb 1 '17 at 13:06
  • $\begingroup$ Look up smallest (or largest) K elements of an array as it is a more common problem statement. I think approach is the same. $\endgroup$ – paparazzo Feb 1 '17 at 13:33
  • 1
    $\begingroup$ @JakeHall: See the answers, and you really need to practice stating questions clearly. $\endgroup$ – gnasher729 Feb 2 '17 at 0:32

Yes, it can be done in $O(n \log k)$ time, using exactly the approach you hinted at.

You're going to do a linear scan over the array, from left to right. At each step, you check whether the max of the last $k$ elements is more than twice the min of the last $k$ elements.

To compute the max and min efficiently, you'll maintain a max-heap of the last $k$ elements, and a min-heap of the last $k$ elements. Each time you move one element to the right, you add an element to each heap (insert $A[i]$ into the heap) and remove an element from each heap (delete $A[i-k]$ from the heap).

To remove elements from the heap, have two auxiliary arrays, $B$ and $C$. $B[i]$ maintains a pointer to where $A[i]$ is stored in the max-heap, and $C[i]$ maintains a pointer to where $A[i]$ is stored in the min-heap. To reduce space consumption, you can arrange that these two auxiliary arrays are of length $k$ rather than length $n$, if that is important.

  • $\begingroup$ Isn't you meat " B[i] maintains a pointer to A[i-k]"? As you want to remove A[i-k] when you go from i to i +1? $\endgroup$ – noman pouigt Feb 2 '17 at 2:30
  • $\begingroup$ @nomanpouigt, what I wrote is fine, I think. When you want to remove $A[i-k]$ from the max-heap, you look up $B[i-k]$ to find a pointer to where it is stored. $\endgroup$ – D.W. Feb 2 '17 at 5:07

I'd look at your conditions first. If |a-x| ≤ k, and |b-x| ≤ k, and b = 2a, then |x| ≤ 3k, |a| ≤ 2k, |b| ≤ 4k.

So you make one pass in O (n) keeping only array elements with absolute value ≤ 4k, and elements > 3k must be even. You can use a hash table to also remove duplicates quickly. This works in practice in O (n). Now obviously the rest relies on how many numbers are left, say m numbers. So the time is O (n) plus some function of m. I actually don't think the size of k is relevant unless you take into account that with enormous k basic operations take time in O (log k). (So if you don't have 64 bit numbers, but 64,000 bit numbers, then things will slow down. I'll ignore this).

You sort the array in O (m log m). Then you scan the list using three pointers; you find values a in the list such that b = 2a is also in the list, and then you check whether any x in the intersection of [a-k, a+k] and [2a-k, 2a+k] is in the list. That should happen in linear time O (m).

(Reading D.W.'s answer, we seem to be interpreting "any two elements within k distance" in a totally different way.)

  • $\begingroup$ I think this is a misunderstanding of the question (which is understandable, as I found the question is not so easy to understand). We've got an array here, and the conditions are that $A[i] \le 2 A[j]$ for all $i,j$ with $|i-j|\le k$. That's not the same as what you wrote in the first line. In other words, the indices must differ by at most $k$, and the elements at those indices must differ by at most a factor of two. This answer mixes the two up. $\endgroup$ – D.W. Feb 1 '17 at 23:07
  • $\begingroup$ I also read it as "one distance cannot be exactly twice another distance" which again totally changes the algorithm. $\endgroup$ – gnasher729 Feb 2 '17 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.