0
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\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$ Commented Feb 1, 2017 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$ Commented Feb 1, 2017 at 5:59
  • $\begingroup$ Yes, k is part of the input. $\endgroup$ Commented Feb 1, 2017 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$ Commented Feb 1, 2017 at 13:33
  • 2
    $\begingroup$ @JakeHall: See the answers, and you really need to practice stating questions clearly. $\endgroup$ Commented Feb 2, 2017 at 0:32

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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$ Commented Feb 2, 2017 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$ Commented Feb 2, 2017 at 5:07
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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$ Commented Feb 1, 2017 at 23:07
  • $\begingroup$ I also read it as "one distance cannot be exactly twice another distance" which again totally changes the algorithm. $\endgroup$ Commented Feb 2, 2017 at 0:31

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.