# Find all $k$ local maximums in an array of length $n$ in $O(n \log k)$ time

Given a sequence of numbers $a_1, a_2, ..., a_n$, a number $a_i$ is called the $k$ local maximum $\iff i > k$ and $a_i$ is the largest number among the $(k+1)$ numbers $a_{i-k}, a_{i-k+1}, ..., a_i$. Given a sequence of $n$ numbers $a_1, a_2, ..., a_n$, and an integer $k$, I am requested to find all $k$ local maximums in $O(n \log k)$ time.

At first, this seems like a dynamic programming problem, where I first calculate the solution for $k'=1$, and goes from there to $k'=k$, but this approach seems to take $O(nk)$ time.

I have found a possible solution to my problem here , but this also seems to take $O(nk)$ time for my problem, as

1. Build a Cartesian tree of the first $k$ elements. $O(k)$

2. Insert and check whether the $(k+1)$th element is the $k$ local maximum (also remove the leftmost element). $O(k)$

3. Repeat step two until reaching the end of the sequence.

The overall complexity seems to be $O(k) + O((n-k)k) = O(nk)$.

Any help is appreciated. Many thanks.

Hint: Use some data structure that allows insertion, deletion, and search in logarithmic time to maintain a snapshot of the $k$ preceding elements, and use it to determine whether the next element is a $k$-maximum in time $O(\log k)$.