# How to find a pair of array elements whose difference is smaller than the average difference?

How to find a pair of indices $1\le i \le n$,$1\le j \le n$, $i\neq j$ in array $A[1..n]$ such that $0\le A[i]-A[j]\le\frac{max(A)-min(A)}{n-1}$ in $\Theta(n)$ time? max(A) is the max number in the array while min(A) is the min number.

Let $avg=\frac{max(A)-min(A)}{n-1}$. If we sort the array $A$ and calculate the differences of adjacent members then $avg$ is the average difference.

I feel like the question has to do with order statistics (select algorithm) but I don't quite know how exactly.

• Sorting is already $O(nlog(n))$. – fade2black Jul 16 '17 at 14:04
• @fade2black I think there's another solution which doesn't rely on sorting – Yos Jul 16 '17 at 14:06
• Are numbers bounded? – rus9384 Jul 16 '17 at 14:42
• @rus9384 if you mean that the numbers are within a given range, then no we're not given any range – Yos Jul 16 '17 at 14:44
• @rus9384 if we call select algorithm (p.216 CLRS) on the array we can find out the median element in $\Theta(n)$ expected time (although the problem doesn't state that expected time is allowed). Then wouldn't those elements $i,j$ be any elements to the left of the median? (because select uses partition routine which shuffles every element lesser than the partition to the left) – Yos Jul 16 '17 at 15:53

Hint: to build intuition, suppose I told you that you want to find a pair of elements that differ by at most $1000$. Can you think of any way to find such a pair of elements? Would looking at the decimal representation of the numbers help? Could you characterize what their decimal representation would have to look like?
• Does your solution result in linear time complexity? I think I know the solution to the problem if sorting is involved: we sort the numbers, the numbers to the left of the median of the sorted array should satisfy the condition. But this results in $\Theta(n\log n)$ complexity – Yos Jul 16 '17 at 18:36