The following is a programming interview question: Given 3 sorted arrays. Find(x,y,z), (where x is from 1st array, y is from 2nd array, and z is from 3rd array), such that Max(x,y,z) – Min(x,y,z) is minimum. This question is discussed here: http://www.careercup.com/question?id=14805690
One possible solution discussed in the career cup page is the following: “Take three pointers. Each to the first element of the list. then find the min of them. compute max(xyx)-Min(xyz). If result less than till now result change it. increment the pointer of the array which contains the minimum of them”
My question is, how can we prove the correctness of this algorithm? If not, can we come up with cases where the algorithm fails. And if so, what is a correct algorithm to solve this problem with the proof.
5
Lets call sorted arrays A1, A2, A3. We have three indices i1, i2, i3. We want to find one triple (i1,i2,i3) such that max(A1[i1], A2[i2], A3[i3]) – min(A1[i1], A2[i2], A3[i3]) is minimal. At beginning i1 = i2 = i3 = 0.
One possible way is to try all triples (i1, i2, i3) for 0 <= i1 < A1.lenght, 0 <= i2 < A2.lenght, 0 <= i3 < A3.lenght. But many of those triples will be unnecessary to check.
Without loss of generality (this is just for easier talking about arrays) let A1[i1] <= A2[i2] <= A3[i3]. We will do one increment in this block.
There is no sence to try triples (j, i2, i3) for j < i1, because arrays are sorted and A1[j] <= A1[i1] which is minimum. Lets pretend we already tried all these (j, i2, i3).
There is no sence to try (i1, i2, j) for j > i3 because A3[i3] <= A3[j].
By trying triples (i1, j, i3) for arbitrary j we can go worse (min will be less or equal and max will be higher or equal).
We tried indices less than i1, i2, i3. We reasoned triples (j < i1, i2, i3) and (i1, j, i3) are unnecessary, (i1, i2, j>i3) too. Same arguments for (j <= i1, k, l = i3). Decrementing i3 is no use as we tried (actually or reasoned about it) this triple before increasing the third index.
We are left to increasing i1 which is index of min in the triple. After this the difference might get worse or A1[i1+1] is not minimal, but we proceed the same way.
2
The algorithm has as loop-invariant where we know the smallest value of max(x, y, z) - min(x, y, z) for all possible values of x, y, or z smaller than the current values.
To start with x, y, and z are the smallest possible, so the invariant is true at the beginning. At the end, x, y, and z are the largest possible, so they cover all possible values, and we have the answer.
Given some values of x, y, z, if we know the optimal value of max(x, y, z) - min(x, y, z) for smaller values, then any better value would require incrementing x, y, or z.
If we don’t increment the minimum of them then every larger value of x, y, or z can only increase the value of max(x, y, z) - min(x, y, z) because the maximum can only increase, and the minimum will stay the same. So the minimum is incremented to the smallest value that could possibly be better than the one we have, which maintains the loop-invariant.
4