# Find two numbers in array $A$ such that $|x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

I'm struggling with the following question:

Let $$\langle a_0, a_1,\dots,a_n\rangle$$ be a sequence of real numbers, and let $$M = \max\{a_0, a_1, .... a_n\}$$ and $$m = \min\{a_0, a_1, .... a_n\}$$.

a. Prove that there are two numbers in the sequence $$x,y$$ such that $$|x-y| \leq \frac{M-m}n$$.

b. Write an algorithm that finds those numbers in linear time.

I've manage to prove part a, but am struggling with part b. I've tried to find a way to find the two element in the array that have the smallest difference, but couldn't find a way to do it in $$\Theta(n)$$. It should be something related to select algorithm and medians.

This is an interesting question.

Here is an algorithm.

1. Iterate through the array to obtain $$m$$ and $$M$$. If $$m=M$$, we are done. Otherwise, let $$\delta=\frac{M-m}n$$.
2. For $$i=0,1,\cdots,n+1$$, let $$L_i$$ be an empty list of numbers.
3. Iterate through the array again. For each $$a_j$$, if $$\lfloor (a_j-m)/\delta\rfloor=k$$, then append $$a_j$$ to $$L_k$$ and $$L_{k+1}$$.
4. Iterate through $$L_0, L_1, \cdots, L_{n+1}$$. Skip $$L_k$$ if there is at most one number in it. Otherwise process $$L_k$$ as follows.
• If there are two numbers, compute their difference. If it is not more than $$\delta$$, we are done.
• If there are three numbers or more, select arbitrarily three of them. Compute all three differences between each pair of them. There must be one pair of numbers whose difference is smaller than $$\delta$$. Select that pair and we are done.

It is not difficult to see the above algorithm is correct and its time-complexity is $$\Theta(n)$$.

The above algorithm could be sped up if $$L_k$$ or $$L_{k+1}$$ is processed just as in step 4 while we are still running step 3. It would be an interesting but hard problem to determine when will be the optimal time to start processing, assuming for example, $$a_j$$'s are uniformly and independently distributed in $$[m,M]$$. Starting from $$a_{n//2}$$ (or $$a_{\lfloor n/\log n\rfloor}$$ or even $$a_{\lfloor n/\sqrt n\rfloor}$$?) should improve the speed in general, I believe. However, the worst time-complexity cannot be better than $$\Omega(n)$$.

Instead of step 3, we could also put $$a_j$$ to $$L_{k}$$, $$L_{k+1}$$ and $$L_{k+2}$$ if $$\lfloor 2(a_j-m)/\delta\rfloor=k$$ and adapt step 2 and 4 accordingly.

It might be interesting how I found this algorithm. I literally recited Polya's principle, "do you know a related problem?". I recalled that finding duplicate elements in an array using hash table takes linear time of $$n$$. Could I apply that conclusion? Or the way of using hash table? What is a hash table and how can I create a hash here? If I can put nearby numbers in the same slot, I can considered them as the same, then the algorithm might work. The it dawned on me that I could use the location of $$a_j$$ as "its hash". However, two numbers that are very close could be mapped to different hashes, which breaks the promise. If one hash is not enough, how about two hashes? I could almost see the light on the other side of the tunnel. After a few minor adjustments, I arrived at the current answer. (Somehow I missed Yuval's nice method by divide and conquer, which, in hindsight, should not have been difficult to find.)

Motivated by Yuval's emphasis on randomization and practice, I would like to ask the following question.

Let $$n+1$$ numbers be (uniformly and) independently distributed in $$[0,1]$$. Is there an algorithm that finds two elements whose absolute difference is not greater than $$1/n$$ with sublinear average time-complexity? (I believe the naive algorithm that inserts $$a_j$$ into a (balanced) binary search tree works. Who has a proof?)

• What's $\delta$? – Yuval Filmus Dec 1 '18 at 23:21

Let $$z$$ be the median of $$A$$, and split $$A$$ into two subarrays $$B,C$$: the array $$B$$ consists of all numbers at most $$z$$ (including $$z$$), and the array $$C$$ consists of all number at least $$z$$ (including $$z$$). Assuming for simplicity that $$n$$ is even and that all elements in $$A$$ are distinct, we can write $$B = b_0,\ldots,b_{n/2}, \\ C = c_0,\ldots,c_{n/2},$$ where $$b_{n/2} = c_0 = z$$. Define $$\delta(X) = \frac{\max(X) - \min(X)}{\mathrm{len}(X)-1}$$. Then $$\delta(B) + \delta(C) = \frac{z-\min(A)}{n/2} + \frac{\max(A)-z}{n/2} = \frac{\max(A)-\min(A)}{n/2} = 2\delta(A),$$ and so $$\min(\delta(B),\delta(C)) \leq \delta(A)$$. This implies that we can recurse on either $$B$$ or $$C$$.

Using a linear time algorithm for finding the median, we obtain an algorithm whose running time satisfies the recurrence $$T(n) = T(n/2) + \Theta(n)$$, whose solution is $$T(n) = \Theta(n)$$. Details left to you.

Let me comment that $$\min(\delta(B),\delta(C)) \leq \delta(A)$$ whatever the sizes of $$B,C$$ are (this requires a simple adaptation of the above proof). This suggest a randomized algorithm running in expected linear time, which simply chooses $$z$$ at random. This is possibly more efficient in practice.