Algorithm for finding 2 items with given difference in an array

Question

I am given an array of real numbers, A. It has n+1 elements. It is known that there are at least 2 elements of the array, x and y, such that:

 abs(x-y) <= (max(A)-min(A))/n

I need to create an algorithm for finding the 2 items (if there are more, any couple is good) in O(n) time.

I've been trying for a few hours and I'm stuck, any clues/hints?

Thanks!

Answer 1

Let's re-word the problem: we're to find two elements, such that abs(x-y) <= c, where c is a constant, that we can find in O(n) time. (Indeed, we can compute both max(A) and min(A) in linear time and just assign c=(max-min)/n).

Let's imagine we have a set of buckets, so that in first bucket elements 0<=x<c are placed, in the second bucket elements c<=x<=2c are placed, etc. For each element, we can determine its bucket for O(1) time. Note that the number of buckets occupied will be not more than the number of elements in array.

Let's iterate the array and place each element to its bucket. If in the bucket we're going to place it, there already is another element, then we've just found the proper pair of x and y!

If we've iterated the whole array and every element has fallen into its own bucket, no worries! Iterate the buckets now (there is not more than n buckets, as we've said above) and for each bucket element x, if in the next bucket y element is such that abs(x-y)<=c, then we've found the solution.

If we iterated all the buckets and found no proper elements, then there is no solution. OMG, I really missed that pigeonhole stuff (see the other answer).

Buckets may be implemented as a hash map, where each bucket holds one array index (placing element in bucket will look like this: buckets[ a[i] / c] = i). We compute c in O(n) time, assign items to buckets in O(n)*O(1) time (O(1) is access to hash map), traverse buckets in O(n) time. Therefore, the whole algorithm is linear.

Answer 2

woo I got it! The trick is in the Pigeonhole Principle.

Okay.. think of the numbers as being points on a line. Then min(A) and max(A) define the start and end points of the line respectively. Now divide that line into n equal intervals of length (max(A)-min(A))/n. Since there are n+1 points, two of them must fall into one of the intervals.

Note that we don't need to rely on the question telling us that there are two points that satisfy the criterion. There are always two points that satisfy it.

The algorithm itself: You can use a simplified form of bucket sort here, since you only need one item per bucket (hit two and you're done). First loop once through the array to get min(A) and max(A) and create an integer array buckets[n] initialized to some default value, say -1. Then go for a second pass:

for (int i=0; i<len; i++) {
    int bucket_num = find_bucket(array[i]);
    if (bucket[bucket_num] == -1)
        bucket[bucket_num] = i;
    else
        // found pair at (i, bucket[bucket_num])
}

Where find_bucket(x) returns the rounded-down integer result of x / ((max(A)-min(A))/n).