# How to check if $m$ numbers in a sequence satisfy a condition, such that all these numbers are spaced apart by at least $k$?

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 = 3, s = 2, s = 1$ and $s, s, s$ 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?

• Have you tried dynamic programming? Apr 15 '18 at 7:31
• 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)$? Apr 15 '18 at 10:46
• 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. 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.