Determining if a list contains two numbers whose difference is less than k 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|&lt;k$, so I have to check $2k$ different elements, which isn't good enough.
Does anybody have any other idea?
Let $f(x) = \lfloor x/k \rfloor$. Create a hash table which stores $f(x_1),\ldots,f(x_n)$; furthermore, for each $y \in \{f(x_1),\ldots,f(x_n)\}$, count how many elements map to $y$, and what is the minimal element mapping to $y$.

If any of the cells contains more than one element, then these two elements are at a distance of less than $k$. Otherwise, go over all elements, and for each $x_i$, compare $x_i$ to the minimal element mapping to $f(x_i)+1$, checking whether the two elements are at distance less than $k$. If no elements at distance less than $k$ have been found in this way, then no such elements exist.