CODEWITHSUNDEEP
arraysalgorithmsorting
user1071840
user1071840

Reputation: 3592

Three nearby numbers in three arrays

Given three sorted floating-point arrays a[], b[], and c[], design a linearithmic algorithm to find three integers i, j, and k such that |a[i] - b[j]| + |b[j] - c[k]| + |c[k] - a[i]| is minimum.

I do have a solution in mind but I don't think that is linearithmic. This is what I have right now:

 assume minDiff = // some huge value

 for each entry in 'a'
   find an entry closest to it in 'b' and call it 'closestToA'
   find an entry closest to 'closestToA' in 'c' and call it 'closestToB'
   compute the diff: 
         int currDiff = Math.abs(a[i] - closestToA) + Math.abs(closestToA - closestToB) + Math.abs(closestToB - a[i]);
   Replace minDiff with currDiff, if currDiff < minDiff

First of all, I'd like to know if there is any better solution? If not, then am I right in thinking that this solution doesn't have linearithmic complexity? The closest number can be found using binary search.

The question is from "Algorithms - 4th Ed." by Robert Sedgewick and Kevin Wayne and I'm preparing for an upcoming interview.

Somewhat Similar question: Match Three or More Nearest Numbers from arrays

Upvotes: 5

Views: 1326

Answers (2)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

The following algorithm is almost like merging three sorted arrays into one sorted one.

Keep one pointer for each array (i,j,k for A, B and C respectively). Initialize them to 0.

Then compute the difference between A[i], B[j], C[k] and update the lowest value achieved till now if necessary.

Increment the index in the array for which 

array[index] =  min(A[i], B[j] and C[k])

if it has not reached the end.

That is:

If ( A[i] is the least ), then increment i.
else If ( B[j] is the least ), then increment j.
else increment k.

Keep doing the above till any one index runs past the end or you find a situation where all three A[i], B[j] and C[k] are equal.

EDIT:
If there are two duplicate candidates (say A[i] == B[j]), then increment both i and j. See for yourself why.

Also, if A[i+1] == A[i], then simply increment i again.
End Edit:

The above algorithm has O(N) time complexity.

Proof of correctness:
As shown by other answer, the difference depends only on two extremes of A[i], B[j], C[k].

So if A[i] < B[j] < C[k], then difference = 2*(C[k] - A[i]). Hence if we increment either j or k, then the difference can only increase. Hence we increment i.

Upvotes: 2

Barak Itkin
Barak Itkin

Reputation: 4877

Let us look at some potential ordering of the elements:

a[i] < b[j] < c[k]

Then we can see the following claim holds:

Target = |a[i] - b[j]| + |b[j] - c[k]| + |c[k] - a[i]|
       = b[j] - a[i] + c[k] - b[j] + c[k] - a[i]
       = 2 * (c[k] - a[i])

So, for any possible ordering, this is the minimization of the difference between two elements in two different arrays. So, simply minimize for every possible combination (a and b, b and c, c and a) as shown in the question you gave a reference to (can be done in linearithmic time for each pair).

Once you found the minimization for a pair, finding the matching element from the third array should be quite easy - simply go over that array and check each element.

Upvotes: 3

Related Questions