title: Find the maximum distance between two elements that don't differ by more than k
body: <p>Given an array arr, find the maximum abs(i-j) such that abs(arr[i] - arr[j]) &lt;= k.</p>
  
  <p>After a lot of thought, I came up with the following algorithm,</p>
  
  <pre><code>1) Create a new array of pair&lt;arr[i], i&gt; (say arrayIndexPairs)
  2) Sort this arrayIndexPairs based on the array value (first of pair).
  3) Build a segment tree on the index (second of pair) with the arrayIndexPairs so that we can answer range max queries
  4) for i &lt;- 0 to n-1
      4.1) rightIndex = Binary search the array values (first of pair) for ceil(arrayIndexPairs[i].first) in the interval [i+1, n-1]
      4.2) int maxIndex = rangeQueryForMax(i+1, rightIndex)
      4.3) result = max(result, maxIndex - i);
  return result
  </code></pre>
  
  <p>The complexity is <code>O(n log n)</code> for the sort + for every element we do a binary search <code>O(log n)</code> + <code>rangeQuery</code>, <code>O(log n)</code>. The overall time complexity is <code>O(nlogn + n*2*logn)</code> which is asymptotically <code>O(nlogn)</code>.</p>
  
  <p>Is the approach correct? Is is possible to formulate a linear time solution? I tried using hashmaps but find it very hard to arrive at a linear solution.</p>