Minimum Triplet

Problem:
===========
You are given 3 integer arrays A, B and C of length n1, n2 and n3 respectively. All arrays are sorted. We define triplet of these 3 arrays as (x,y,z) where x is any integer from A, y from B and z from C. We define distance of triplet as maximum difference among triplet elements, i.e. Maximum of x – y, y – z or z – x. Write a program to find minimum triplet distance. (means there are n1*n2*n3 number of possible triplets are possible...among all triplets which triplet has minimum distance...Give only distance, but not triplet elements). Your program must be as much efficient as possible.


Solution:
=========
int incMin(int *i, int *j, int *k); helper function that will increase the minimum of the three input indexes of 3 arrays, e.g. if a[.i] is least out of a[.i], b[j], c[k] then it will do i++ and if any one goes out of bound, it will return ERROR

int windowSize(int i, int j, int k); helper function that returns the current window size = max(a[.i], b[j], c[k]) - min(a[.i], b[j], c[k])

now the concept goes as following:
we start with a window of 3 elements, one from each array. and keep altering the window as required and keep updating the minimum window found so far.

minWindow = 99999; // some very large value
returnVal = 0;
i = j = k =0;

while(returnVal != ERROR) //while one of the arrays does not exhaust
{
..currMinWindow = windowSize(i, j, k);

..if(currMinWindow < minWindow)
....minWindow = currMinWindow;

..returnVal = incMin(&i, &j, &k); // this will increase one of the i, j, k
}

int incMin(int *i, int *j, int *k)
{
..if(a[*i] < b[*j])
..{
....if(a[*i] < c[*k])
....{
......if(i<sizeof(A))
........(*i)++; //a[.i] is minimum, so inc i
......else
........return ERROR;
....}
....else
.....{
........if(k < sizeof(C))
..........(*k)++; //c[k] is minimum, so inc k
........else
..........return ERROR;
......}
..}
..else
..{
....if(b[*j] < c[*k])
....{
......if(j < sizeof(B))
........(*j)++; //b[j] is minimum, so inc j
......else
........return ERROR;
....}
....else
....{
......if(k < sizeof(C))
........(*k)++; //c[k] is minimum, so inc k
......else
........return ERROR;
....}
..}
}

Powered by ScribeFire.