Find Pairs Within a Bound Distance

Today I attempt to solve another problem:

-------------------------------------------------------------------

PROBLEM: Given an array A with n unsorted integers, find a pair of numbers (x,y) in the array such that:

     (1)        |x-y| ≤ (max - min) / (n-1)

               where min and max are the minimum and maximum elements in array A.

               By the way, I want to make sure you know that when you are given array A,
               you are not given min and max, you have to find them out.

      ALSO: The solution algorithm needs to run in linear-polynomial time, just so you know :)

-------------------------------------------------------------------

I will attempt to solve this problem from my home laptop, which is increased difficulty since the keyboard is harder than a 1950's typewriter.

-------------------------------------------------------------------

SOLUTION:

I propose a solution which I claim to run in linear-polynomial time.

Here it is:

let min = undef;

let max = undef;

for i = 0 to i == (A.Length - 1) do

   if (A[i] < min OR min == undef)

       min = A[i];

   if (A[i] > max OR max == undef)

       max = A[i]; 

Now that we have min and max, I calculate a new variable called distBoundary as:

let distBoundary = (max - min) / (n-1);

Now I create a new array called B, with length of (n-1).

And I do the following:

let B = new ArrayOfLength(n-1);

let B[i] = undef for all  0≤i<B.Lentgh; 

let B[0] = min;

let B[n - 2] = max;

for i = 1 to i == (A.Length - 2) do

    let bIndex = (A[i] - min) / distBoundary;

    if (B[bIndex] == undef)

       B[bIndex] = A[i];

    else 

       return pair(B[bIndex], A[i]);

That's it. :)

Question: Why does it work?

Answer: Because it finds the correct answer and it does it in linear-polynomial time. 

It runs in time 2*O(n), which is linear-polynomial time. The first time we loop A that O(n), the second time it's O(n)... hence O(n) + O(n).

Note that the pseudo-code is a little scrappy, but I just meant to illustrate the main idea of the solution.

Why is it correct?

Consider the interval between min and max. 

Divide that interval in segments of length distBoundary.

|min------------------|------------------|------------------|.......|------------------max|

                                              (n-1) segments of length distBoundary between

Each one of those segments is a position on created array B.

There are (n-1) segments of length distBoundary between min and max inclusive.

We know there are n-2 integers in array A that have a value between min and max.

If two numbers x,y are in the same segment of length distBoundary then those two numbers satisfy proposition (1).

Notice that min is already on the first segment, and max is on the last segment, leaving only n-3 segments free and n-2 integers in A that must be between min and max... hence because of the famous pigeons property... if you have n-2 pigeons and n-3 pigeon houses... two pigeons are going to have to live together right? :)

QED?