Determining if a list contains two numbers whose difference is less than k

Question

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?

Answer 1

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.

Answer 2

Here is another suggestion. Use radix sort to sort the integers, than check if the difference between any two successive elements is less than k. Its solves your problem if you assume that radix sort is O(n)