1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is a max heap capable of doing that? I am actually looking at its Wiki page trying to figure out why its insertion is O(log n)... $\endgroup$ – user23245 Nov 1 '14 at 7:14
  • $\begingroup$ There are many data structures with this property. $\endgroup$ – Yuval Filmus Nov 1 '14 at 7:16
  • $\begingroup$ Sorry to bother you again, but is any of these data structures capable of preserving the original sequence ordering in some way? Because I will need to remove the nodes one at a time according to their input order. $\endgroup$ – user23245 Nov 1 '14 at 7:38
  • $\begingroup$ You will manage somehow. Think about the problem for a couple more hours before you come asking for any more help. $\endgroup$ – Yuval Filmus Nov 1 '14 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy