# 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|<k$, so I have to check $2k$ different elements, which isn't good enough.

Does anybody have any other idea?

• 1. Do you mean their absolute difference |x-y|, or the regular difference $x-y$? 2. Is the group of elements is sorted or not? – user3563894 Aug 30 '18 at 15:33
• @user3563894 1. i mean their absoulute difference, if it is their regular difference , i have to show that their exist x and exist y, such that $y<x+k$ , so i may take x as the maximum . 2. i know nothing about the elements, except that they are positive and natural. – Moshe Levy Aug 30 '18 at 17:53

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.
• Hey thank you, some questions: 1. $f(x)$ is the mapping function of the hash table? 2. Dont we have to check $f(x_i)-1$ either,and compare it to the maximum? – Moshe Levy Aug 30 '18 at 17:55
• 1. The hash table is on top of $f(x)$. 2. We don't, since it's enough to find $i,j$ such that $0 < x_j - x_i < k$. – Yuval Filmus Aug 30 '18 at 21:25