Take three pointers p1, p2 and p3 respectively to the arrays A[]

**,**B[] and C[].1. Place all of them at 0th index and minDistance = some very large number

2. Now, find the max and min of the elements pointed to by the pointers.

3. Calculate dist = max - min. if dist is less than minDistance then Store p1,p2 and p3 in index1, index2, index3 and store dist in minDistance. Now, our job is to minimize this dist.

4. Its obvious that dist will be minimized only if we increment the pointer at the min element. Hence, increment the min pointer and repeat step 2.

4. Its obvious that dist will be minimized only if we increment the pointer at the min element. Hence, increment the min pointer and repeat step 2.

Implementation of above logic is as follows --

int max(int i, int j, int k)

{

return (i > j) ? ( i > k ? i : k) : (j > k ? j : k);

}

int min(int i, int j, int k, int& arr)

{

int temp = (i < j) ? ( i < k ? i : k) : (j < k ? j : k);

arr = (temp == i) ? 0 : (temp == j ? 1 : 2);

return temp;

}

void FindTriplet(int *a, int *b, int *c, int lenA, int lenB, int lenC)

{

int index[3] = { 0 };

int minArr = 0;

int minDistance = 32767; // Large number

int minIndex[3] = {0};

while(index[0] < lenA && index[1] < lenB && index[2] < lenC)

{

int distance = max(a[index[0]], b[index[1]], c[index[2]]) -

min(a[index[0]], b[index[1]], c[index[2]], minArr);

if(distance < minDistance)

{

for(int i =0; i<3; minIndex[i++] = index[i]);

if(0 == (minDistance = distance) )

break;

}

index[minArr]++ ;

}

cout<<"Minimum Distance :: "<<minDistance<<"\nAt indices\t"<<minIndex[0]<<'\t'

<<minIndex[1]<<'\t'<<minIndex[2]<<'\n';

}

Nice Nishant :)

ReplyDeletefor this solution, did you supose that max(x - y, y - z, z - x) = max(x,y,z) - min(x,y,z)?

ReplyDeletei believe thats not always true. for example, if we have (5,2,-3), then x-y = 3, y-z = 5, z-x = -8 and max(x - y, y - z, z - x) = 5 , but max(x,y,z) - min(x,y,z) = 8

@iamavalon

ReplyDeletewe need to take absolute value of the difference between the numbers as it is distance, so whether it is -8 or 8, distance remains 8 units.

ok, but then the problem statement is not correct. in the problem, the distance of a vector (x,y,z) was defined as max(x-y, y-z, z-x), and not as max(|x-y|, |y-z|, |z-x|), |a| being the absolute value of a, which is the same as the max(x,y,z) - min(x,y,z) that your solution used.

ReplyDelete@iamavalon

ReplyDeleteyes, I agree.. correcting now

@Vikash

ReplyDeleteThanks

Thanx man!!!:)

ReplyDeletecan you guide me through the complexity of this algorithm??

ReplyDeleteComplexity would be O(n)

DeleteHi nishant,

ReplyDeleteYour logic needs to be modified for the following scenarios

A:1,2,3,4

B: 1,2,3

C: 5,6

Try your logic and find out the error

I think logic is correct and it is producing right result -

DeleteMinimum Distance :: 2

At indices 2 2 0