Finding difference less than the average in an unsorted array?

Question

Hi,

I need to find 2 elements in an unsorted array such that the difference between them is less than or equal to (Maximum - Minimum)/(number of elements in the array).

In O(n).

I know the max and min values.

Can anyone think of something?

Thank you!

Answer 1

Step 1: Use Bucket Sort. Don't sort the individual buckets.

Should be pretty obvious what to do from here, and how to size the buckets.

Answer 2

1. Number of buckets = 2n.

   values in each bucket = (min + k((max-min)/2n)) <= value < (min + (k+1)((max-min)/2n)).

   0 <= k < 2n

   Range of each bucket = ((max-min)/2n)

2. Assign each element into buckets. Dont sort inside buckets.

3. If any bucket has more than 1 element, the maximum possible difference between them is ((max-min)/2n) . Hence you have your answer.

4. If any two consecutive buckets have more than zero elements each, maximum difference between them is ((max-min)/2n)*2 = ((max-min)/n) . Hence you have your answer.