title: Returning duplicates within a given window size in an array?
body: <p>I saw this question and I have no idea how to do the second part given the time and space constraints:</p>
  
  <p>Given an array of values, design and code an algorithm that returns whether there are two duplicates within k indices of each other? k indices and within plus or minus l (value) of each other? Do all, even the latter, in O(n) running time and O(k) space.</p>
  
  <p>It seems impossible to me to know whether there is a duplicate of a given value within a window size of the value without looking at all values with index difference between k and a[i] but since a[i] might be large, I think that would take O(n^2). Can it be done in O(n)?</p>