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?