Finding a pair in an array that's difference i smaller then MAX-MIN / n-1

Question

I've a problem I struggle to solve. The question is: Given an array A of size $n$, find a pair, $i,j$ so that $$ 0 \le A[i] - A[j] \le \frac{\max[A] - \min[A]}{n-1}$$ now the problem is that time complexity needs to be $O(n)$. Thx in advance

Answer 1

Find min $m$, find max $M$ and then create an array $B$ of $n-1$ elements full of $-1$. Now go through array and for each element $x$ with index $k$ find such $i$ that: $$m+i\frac{M-m}{n-1} \le x \le m+(i+1)\frac{M-m}{n-1}$$ And put $B[i]=k$ if previously we had $B[i]=-1$. If not, that means that the numbers ubder the indicies $B[i]$ and $k$ satisfy your conditions. Also we are bound to find such pair because there are more elements in the original table than in $B$ (pigeonhole principle).

Basically the idea is to divide the interval $[m,M]$ in $n-1$ equal parts and put all the numbers where they belong - there has to be a collision yielding our answer.