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 a linear-time algorithm. Assum $n\ge1$.

• Compute the minimum $m$ and the maximum $M$. If $m=M$, return $a_0$ and $a_1$. Otherwise, let $\delta=\frac{M-m}n$.

• For $i$ from $0$ to $n$, let $\text{slot}_i$ be an empty list of numbers.

• For $i$ from $0$ to $n$, append $a_i$ to $\text{slot}_{\lfloor (a_i-m)/\delta\rfloor}$.

• For $i$ from $0$ to $n$, check whether there are at least two numbers in $\text{slot}_i$. If yes, return any two numbers in $\text{slot}_i$.

• Otherwise, each $\text{slot}$ contains one number. For $i$ from $1$ to $n$, check whether $b_{i}-b_{i-1}\le \delta$, where $b_{j}$ is the only number in $\text{slot}_j$. If yes, return $b_{i-1}$ and $b_{i}$.

It is easy to see the algorithm is correct with time-complexity $\Theta(n)$.

It might be interesting how I found my initial algorithm.

I literally recited George Pólya's principle, "do you know a similar 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 my initial algorithm.

(Somehow I missed Yuval's nice algorithm by divide and conquer, which, in hindsight, should not have been difficult to find.)

StackExchange Computer Science Q#100830, answer score: 6