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.

  • $\begingroup$ Sorting is already $O(nlog(n))$. $\endgroup$ – fade2black Jul 16 '17 at 14:04
  • $\begingroup$ @fade2black I think there's another solution which doesn't rely on sorting $\endgroup$ – Yos Jul 16 '17 at 14:06
  • $\begingroup$ Are numbers bounded? $\endgroup$ – rus9384 Jul 16 '17 at 14:42
  • $\begingroup$ @rus9384 if you mean that the numbers are within a given range, then no we're not given any range $\endgroup$ – Yos Jul 16 '17 at 14:44
  • $\begingroup$ @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) $\endgroup$ – 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?

  • $\begingroup$ 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 $\endgroup$ – Yos Jul 16 '17 at 18:36
  • $\begingroup$ @Yos, try it and find out! $\endgroup$ – D.W. Jul 16 '17 at 18:41
  • $\begingroup$ I don't know how it helps since even sorting for array which has it's elements bounded can be done in linear time. $\endgroup$ – rus9384 Jul 16 '17 at 20:50
  • $\begingroup$ @rus9384, in this case the elements aren't bounded, so you can't necessarily sort in linear time (for instance, counting sort doesn't run in linear time) -- but there are other ways to solve this without sorting. $\endgroup$ – D.W. Jul 17 '17 at 0:30

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.