How to find the longest sub-array within a threshold?
<p>Let's say you have a sorted array of numbers <code>sorted_array</code> and a threshold <code>threshold</code>. What is the fastest way to find the longest sub-array in which all the values are within the threshold? In other words, find indices <code>i</code> and <code>j</code> such that:</p>

<ol>
<li><code>sorted_array[j] - sorted_array[i] &lt;= threshold</code></li>
<li><code>j - i</code> is maximal</li>
</ol>

<p>In case of a tie, return the pair with the smallest <code>i</code>.</p>

<p>I already have a loop-based solution, which I will post as an answer, but I'm curious to see if there's a better way, or a way that can avoid the loop using a vector-capable language or library like NumPy, for example.</p>

<p>Example input and output:</p>

<pre><code>&gt;&gt;&gt; sorted_array = [0, 0.7, 1, 2, 2.5]
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 0.2)
(0, 0)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 0.4)
(1, 2)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 0.8)
(0, 1)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 1)
(0, 2)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 1.9)
(1, 4)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 2)
(0, 3)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 2.6)
(0, 4)
</code></pre>

<p>Most likely, the OP's own answer is the best possible algorithm, as it is O(n). However, the pure-python overhead makes it very slow. However, this overhead can easily be reduced by compiling the algorithm using <a href="http://numba.pydata.org/" rel="nofollow" title="numba">numba</a>, with the current version (0.28.1 as of this writing), there is no need for any manual typing, simply decorating your function with <code>@numba.njit()</code> is enough.</p>

<p>However, if you do not want to depend on <a href="http://numba.pydata.org/" rel="nofollow" title="numba">numba</a>, there is a numpy algorithm in O(n log n):</p>

<pre><code>def algo_burnpanck(sorted_array,thresh):
    limit = np.searchsorted(sorted_array,sorted_array+thresh,'right')
    distance = limit - np.arange(limit.size)
    best = np.argmax(distance)
    return best, limit[best]-1
</code></pre>

<p>I did run a quick profiling on my own machine of the two previous answers (OP's and Divakar's), as well as my numpy algorithm and the numba version of the OP's algorithm.</p>

<pre><code>thresh = 1
for n in [100, 10000]:
    sorted_array = np.sort(np.random.randn(n,))
    for f in [algo_user1475412,algo_Divakar,algo_burnpanck,algo_user1475412_numba]:
        a,b = f(sorted_array, thresh)
        d = b-a
        diff = sorted_array[b]-sorted_array[a]
        closestlonger = np.min(sorted_array[d+1:]-sorted_array[:-d-1])
        assert sorted_array[b]-sorted_array[a]&lt;=thresh
        assert closestlonger&gt;thresh
        print('f=%s, n=%d thresh=%s:'%(f.__name__,n,thresh))#,d,a,b,diff,closestlonger)
        %timeit f(sorted_array, thresh)
</code></pre>

<p>Here are the results:</p>

<pre><code>f=algo_user1475412, n=100 thresh=1:
10000 loops, best of 3: 111 Âµs per loop
f=algo_Divakar, n=100 thresh=1:
10000 loops, best of 3: 74.6 Âµs per loop
f=algo_burnpanck, n=100 thresh=1:
100000 loops, best of 3: 9.38 Âµs per loop
f=algo_user1475412_numba, n=100 thresh=1:
1000000 loops, best of 3: 764 ns per loop
f=algo_user1475412, n=10000 thresh=1:
100 loops, best of 3: 12.1 ms per loop
f=algo_Divakar, n=10000 thresh=1:
1 loop, best of 3: 1.76 s per loop
f=algo_burnpanck, n=10000 thresh=1:
1000 loops, best of 3: 308 Âµs per loop
f=algo_user1475412_numba, n=10000 thresh=1:
10000 loops, best of 3: 82.9 Âµs per loop
</code></pre>

<p>At 100 numbers, O(n^2) solution using numpy just barely beats the O(n) python solution, but quickly after, the scaling makes that algorithm useless. The O(n log n) keeps up even at 10000 numbers, but the numba approach is unbeaten everywhere.</p>

python arrays algorithm numpy