# 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

## 2 Answers

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

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)

• More generally, this approach works whenever the input can be sorted in linear time. Sep 2, 2018 at 0:39