4
$\begingroup$

I recently came across this question and honestly am pretty unsure of how to solve it, or even begin to develop an algorithm to properly solve it..

The question is:

"An array of $n$ integers is correctly positioned with respect to an integer $k$ if for any $k$ consecutive indices in the array, there does not exist values at two indices, $x$ and $y$ such that $x \geq 2$ * $y$ (where $x$ and $y$ are values at 2 indices of the array in a subarray of size $k$). What is an $O(n \log k)$ algorithm to determine if an array is correctly positioned?"

For example: $[5, 6, 7, 4, 5, 9]$ is not correctly positioned if $k = 4$ since in in the interval $[7, 4, 5, 9]$ we have that $9 \geq 4 * 2$.

My thought is to check all potential subintervals like $[0..k]$, $[1..k+1]$, $[2,..k+2]$ using a min-heap but I really can't think that would satisfy the time constraint since it's resulting in building far too many heaps.

Does anyone know how to approach this problem, or have a solution for it?

Having trouble figuring out how to keep track of this sliding window using heaps, and thinking maybe I have to use a min-heap and max-heap? And compare the max to the min for every subinterval using insertions and deletions?

$\endgroup$
  • $\begingroup$ You do not need to re-build the heap each time. Just perform insertions and deletions accordingly. Declare an index$\ i$ such that it refers to the start of a sliding window. The first element of the subinterval has index$\ i$ and the last one has index $ i + k - 1$. this should lead to a$ \ nlogk$ algorithm as required. $\endgroup$ – JhonRayo99 Feb 19 at 16:56
  • $\begingroup$ @HendrikJan how would I keep an additional index for each of the elements? Would each integer in the array be an object that has a value, and an index associated with it? In that case, how would the algorithm correctly find the element with the associated index? I just don't understand how we can "easily delete the first number from the heap w/o having to search for it". Are you suggesting starting from the end of the array instead of the beginning? Also, I edited the question since the array in my example has violations of the condition all over the place. $\endgroup$ – fibonnaci_0_1_1 Feb 19 at 18:24
  • $\begingroup$ @JhonRayo99 Right, but should I have a min-heap and a max-heap to properly compare the min and max for every subinterval? If I only keep a pointer index $i$ then I also have to know when I extract the min, what index that is as well, right? If the min is extracted and it's the last element in the subinterval sliding window, then I have to find a new min on the next insertion. Could you please elaborate on how I would perform insertions and deletions accordingly? $\endgroup$ – fibonnaci_0_1_1 Feb 19 at 18:26
  • $\begingroup$ You can delete any element from a heap in$\ O(logn)$ time if you know where it is in the heap. So just keep a reference to the first element in the subinterval. $\endgroup$ – JhonRayo99 Feb 19 at 18:46
  • $\begingroup$ If I do that though, I wouldn't just need a reference to the first element in the subinterval I'd also need references to other elements in the subinterval, right? For example with the array: $[5,6,7,4,5,9]$ If I create a min-heap of size 4 with $[5, 6, 7, 4]$ and extract the min which is $4$, I'd need to keep $4$ to compare it to the next subinterval $[6, 7, 4, 5]$ and add the next $5$ to the heap, so the heap again will be $[5, 6, 7, 5]$ but I'll need to compare the max from this subinterval to $4$ which was already extracted.. Do you see where my confusion is stemming from? $\endgroup$ – fibonnaci_0_1_1 Feb 19 at 19:09
7
$\begingroup$

Despite common belief, maintaining the maximum (or minimum) element out of the last $k$ elements does not involve a $O(\log k)$ factor, and can be done in amortized $O(1)$. Using this twice (once for max and once for min) you can solve your problem in $O(n)$.

The trick is done using a monotonic double-ended queue, one where all the elements are either in descending or ascending order. Furthermore, for each element we keep track of the index we encountered it, so we can invalidate it from the queue.

Suppose that we iterate over elements in a stream, and wish to maintain the minimum value (the maximum is analogous). Let's call the current value $x$ and the current index $i$. We first initialize an empty double-ended queue $Q$ and start iterating:

  1. Remove all elements from the queue that would be made irrelevant by $x$. Since we know our queue is in ascending order, this is very simple, we keep removing elements from the back that are bigger than $x$. They are now irrelevant for the window, as $x$ is newer and smaller.

    while not empty(Q) and peek_back(Q).value > x:
        pop_back(Q)
    
  2. Add $x$ to the back of the queue, but keep track of its index as well.

    push_back(Q, value=x, index=i)
    
  3. Invalidate old items in the queue. We only have to do this if the item is in the front of the queue, otherwise its harmless (this lazy removal is what allows us to keep $O(1)$ time).

    while peek_front(Q).index <= i - window_size:
        pop_front(Q)
    
  4. Now peek_front(Q) contains the smallest element in our window, so we can use it and then keep iterating.

Note that steps #2 and #4 are $O(1)$ time, and steps #1 and #3 are $O(r)$ time where $r$ is the number of removed elements from the queue. However since each element is only added once to the queue, the $O(r)$ steps must be amortized $O(1)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, but unfortunately I am not too familiar with double-ended queues (have limited experience implementing them). Is this still possible to do with a heap (or multiple) using similar logic? $\endgroup$ – fibonnaci_0_1_1 Feb 19 at 22:25
  • $\begingroup$ @fibonnaci_0_1_1 A heap is vastly more complicated than a double-ended queue. A double-ended queue is just a linear data structure that you can quickly append to/remove from on either side (as apposed to a regular dynamic array, where only appends/removals at the end are fast). You can also implement them using linked lists or ring buffers. $\endgroup$ – orlp Feb 19 at 22:32
  • $\begingroup$ Ah okay, thanks! I'm familiar with queues and you're definitely right that a double-ended queue is less complex than this. That makes sense. Thank you! $\endgroup$ – fibonnaci_0_1_1 Feb 20 at 0:32
  • 4
    $\begingroup$ Nice! This is a beautiful solution! $\endgroup$ – D.W. Feb 20 at 5:07
  • $\begingroup$ I think I will use this in my lecture notes as an example of the application of a double ended queue. $\endgroup$ – Hendrik Jan Feb 20 at 12:59

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.