Interview Question with Arrays and Consecutive Subintervals

Question

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?

Answer 1

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