# 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|, 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? Aug 30, 2018 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. Aug 30, 2018 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? Aug 30, 2018 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$. Aug 30, 2018 at 21:25