Given a list with $n$ positive elements and positive number $k$, determine whether there are two numbers whose difference is less than $k$.
The average time complexity should be $O(n)$, and the memory should be $O(n)$ as well.
My attempt: initialize a hash table, and insert every element from the list to the hash, all of this takes $O(n)$ time on average.
Now, scan the list. Say the the elements are $x_1,x_2, \dots, x_n$.
Assume we scan $x_i$ then if we have in the list an appropriate element, it should fulfill $|x_i-x_j|<k$, so I have to check $2k$ different elements, which isn't good enough.
Does anybody have any other idea?