3
$\begingroup$

Given input sequence $x_1,...,x_n$, find the longest contigous subsequence $x_i,... x_l$ where each pair $(x_j,x_k)$ satisfies that $|x_j - x_k| \le p$.

I have come up with simple $\mathcal{O}(n^2)$ solution.

O(n^2) solution

I'm sure there is a better way so I'm looking for $\mathcal{O}(n)$ or at least $\mathcal{O(n \log n)}$ solution. Thanks for any help!

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Mar 6 '18 at 18:48
  • 1
    $\begingroup$ But what's your question? $\endgroup$ – Raphael Mar 6 '18 at 18:48
1
$\begingroup$

You can solve this in $O(n\log n)$ using a Range Minimum Query data structure. This is a data structure that given two indices $i \leq j$ return $\min(x_i,\ldots,x_j)$. We can construct a data structure that answers such queries in $O(1)$ time using $O(n\log n)$ preprocessing. The idea is to compute $\min(x_i,\ldots,x_j)$ for every pair $i \leq j$ such that $j-i+1$ is a power of 2. This can be accomplished in time $O(n\log n)$ using the identity $$\min(x_i,\ldots,x_{i+2^{\ell+1}-1}) = \min\bigl(\min(x_i,\ldots,x_{i+2^\ell-1}),\min(x_{i+2^\ell},\ldots,x_{i+2^\ell+2^{\ell}-1})\bigr). $$ Using this information, we can compute each range minimum query as follows. Given $i\leq j$, let $2^\ell$ be the largest power of 2 such that $2^\ell \leq j-i+1$; we assume that we can compute $\ell = \lceil \log_2 (j-i+1) \rceil$ in constant time. Then $$ \min(x_i,\ldots,x_j) = \min\bigl(\min(x_i,\ldots,x_{i+2^\ell-1}), \min(x_{j-2^\ell+1},\ldots,x_j)\bigr). $$

For each $i$, we use binary search to compute in time $O(\log n)$ the maximal $\ell \leq i$ such that $\min(x_\ell,\ldots,x_i) \geq x_i-p$ and the minimal $r \geq i$ such that $\min(x_i,\ldots,x_r) \geq x_i-p$. Thus $x_\ell,\ldots,x_r$ is the largest interval satisfying your constraint in which $x_i$ is the maximal point. Taking the maximum of $r-\ell+1$ over all $i$ reveals the solution to your task.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.