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>Here's a vectorized approach using <a href="https://docs.scipy.org/doc/numpy/user/basics.broadcasting.html" rel="nofollow"><code>broadcasting</code></a> -</p>

<pre><code>def longest_thresh_subarray(sorted_array,thresh):
    diffs = (sorted_array[:,None] - sorted_array)
    r = np.arange(sorted_array.size)
    valid_mask = r[:,None] &gt; r
    mask = (diffs &lt;= thresh) &amp; valid_mask
    bestcolID = (mask).sum(0).argmax()
    idx = np.nonzero(mask[:,bestcolID])[0]
    if len(idx)==0:
        out = (0,0)
    else:
        out = idx[0]-1, idx[-1]
    return out
</code></pre>

<p>Sample runs -</p>

<pre><code>In [137]: sorted_array = np.array([0, 0.7, 1, 2, 2.5])

In [138]: longest_thresh_subarray(sorted_array,0.2)
Out[138]: (0, 0)

In [139]: longest_thresh_subarray(sorted_array,0.4)
Out[139]: (1, 2)

In [140]: longest_thresh_subarray(sorted_array,0.8)
Out[140]: (0, 1)

In [141]: longest_thresh_subarray(sorted_array,1)
Out[141]: (0, 2)

In [142]: longest_thresh_subarray(sorted_array,1.9)
Out[142]: (1, 4)

In [143]: longest_thresh_subarray(sorted_array,2)
Out[143]: (0, 3)

In [144]: longest_thresh_subarray(sorted_array,2.6)
Out[144]: (0, 4)
</code></pre>

python arrays algorithm numpy