Suppose we have a sequence $s$ with $n$ elements from $s[1..n]$. I want to check if there exists $m \leq n$ elements in this sequence that each satisfy some simple condition (that can be tested in $O(1)$ for each $s[i]$), such that all of these elements are spaced apart by at least $k$. Is there an algorithm that can achieve this in $O(n)$ time?

For example, suppose we have $s=[3, 4, 13, 2, 6, 4, 1, 9, 11, 5]$ and we are trying to verify if there exists $m=3$ elements that satisfy the condition $s[i] \leq 4$ and are spaced apart by at least $k=2$. This is true because $s[1] = 3, s[4] = 2, s[7] = 1$ and $s[1], s[4], s[7]$ are spaced apart by at least $2$.

A naive solution that I thought of involved iterating through the sequence and recording each $s[i]$ that satisfies the condition, and then for each $s[i]$, trying to find $m-1$ others that don't violate the spacing requirement. I'm not sure how I can do this in $O(n)$ time. Is it possible?

  • 2
    $\begingroup$ Have you tried dynamic programming? $\endgroup$ Apr 15 '18 at 7:31
  • $\begingroup$ If you want to ask about all such 'simple conditions', it would help to give a specific definition of it. Otherwise, I don't think we can do better than answer your specific example of '$s[i]\leq 4$'. Is a 'simple condition' a condition on exactly one element of $s$ that can be tested in $O(1)$? $\endgroup$
    – Discrete lizard
    Apr 15 '18 at 10:46
  • 1
    $\begingroup$ Sorry, I should have clarified. The simple condition can be tested in $O(1)$ for each element $s[i]$, but I'm mostly interested in a condition such as $s[i] \leq q$ or $s[i] \geq q$ where $q$ is an integer. $\endgroup$
    – leynantion
    Apr 15 '18 at 11:05

As Yuval Filmus said in the comment, you can solve the optimization version (finding maximum viable $m$, which is a stronger version) by dynamic programming.

Let $m_i$ be the maximum viable elements of the sub-problem on $s[1..i]$. Consider the sub-problem on $s[1..i]$. An optimal solution has two choices.

  1. It excludes $s[i]$, then it must choose an optimal solution of the sub-problem on $s[1..(i-1)]$.

  2. It includes $s[i]$, then it cannot include $s[i-1],\ldots,s[i-k+1]$, and must choose an optimal solution of the sub-problem on $s[1..(i-k)]$.

Now you can write a recursion formula for $m_i$, and compute $m_1,\ldots,m_n$ in order in $O(n)$ time.


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.