1) Initialise i,j and k to point beginning of three arrays and find
the gap between min value and max value among triplet.
2) Increment the index pointing to minimum value and find min and max
value among new triplet. If the new gap is less then the current min
gap seen so far, update the stored
@Dumanshu:
min dist: you will terminate the algo when atleast 2 of the lists have their
indices reached the end of their respective lists in the process.
On Sat, Jun 18, 2011 at 12:37 AM, Dumanshu duman...@gmail.com wrote:
@Harshal: your terminating condition would be -
lets say we have set the
@Ashish: In ur example you have found a min distance for a and c. Now
to proceed because we have to find out min distance for two out of
three arrays with the third array in between i.e. u need to find
occurrence of a c b or a b c or b a c or ... in the merged array. Now
quite possible these
I have come up with this approach. Take first two arrays and compute the min
absolute difference between two elements. Then with this mingap2 between A1
and A2, add each element and check what is the least value possible.
Below is the code. Think it should work. I have not considered negative
a 1,10,12,14,16
b 5,6,9,12
c 16,19,22,25
this approch will fail
the fact that two pointers should move atleast to find minDistance is not
getting addressed completely in this solution
in this example min D = 5-1=4 to start with
then pointer in arr a moves, abs(5-10), abs(10-16) both are
@Ashish: could u plz explain ur algo in detail. walk over the merged
list to get adjacent min distance and different tags this would be of
the order O(m*n) say we merge A1 A2 of size m and n respectively.
Also, now how do u go ahead with the 3rd array? didn't get ur
solution.
Harshal's solution
say the arrays are
a 6,7,9
b 3,4,5
c 1,2,8
the merged array would be
1c
2c
3a
4b
5b
6a
7a
8c
9a
1c,2c cant be compared as they are from same array..next is 3a this implies
3-2 =1 is min distance
P.S: you can merge these in O(m+n+p) [merge from bottom as they are already
sorted]
Best
@Harshal: your terminating condition would be -
lets say we have set the pointers to index 0 of each to get the min
distance.
for index 0 set the min_dist overall to the max distance among the 3
pairs. Now increase the pointer with the minimum value and check the
max distance between pairs. If
