3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – user3563894 Aug 30 '18 at 15:33
  • $\begingroup$ @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. $\endgroup$ – Moshe Levy Aug 30 '18 at 17:53
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Moshe Levy Aug 30 '18 at 17:55
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Aug 30 '18 at 21:25
0
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ More generally, this approach works whenever the input can be sorted in linear time. $\endgroup$ – Yuval Filmus Sep 2 '18 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.