Finding all local $k$-maximums in sequence $a_1, a_2, \ldots a_n$.

Question

For given sequence of numbers $a_1, a_2, \ldots, a_n$ we say that $a_i$ is $k$-local maximum, if $i > k$ and $a_i$ is largest of numbers $a_{i - k}, a_{i-k+1}, \ldots, a_i$.

How can we find all $k$-local maximums in running time $\mathcal{O}(n \log k)$? Algorithm takes integer $k$ and sequence $a_1, a_2, \ldots, a_n$.

Answer 1

Insert $a_1,a_2,\ldots a_k$ into a skip-list $L$.

Create a $k$-sized array (called, say, $A$) with pointers to the nodes $a_1,a_2,\ldots a_k$ are stored in inside the skip list.

Next, for $i\in \{k+1,k+2,\ldots n\}$:

1. If $a_i\geq \max (L)$, then report $a_i$ as a $k$-local maximum.
2. Delete the node pointed at by $A[i \mod k]$ from $L$.
3. Add $a_i$ to the $L$.
4. Set $A[i \mod k]$ to point at the newly created node.

Overall runtime is $O(n\log k)$, as every iteration takes $O(\log k)$ time.