wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Array (find min of |A[i]-B[j]|)
        
(Message started by: witee on Jul 28th, 2010, 3:51pm)
Title: Array (find min of |A[i]-B[j]|)
Post by witee on Jul 28th, 2010, 3:51pm
Given 2 sorted arrays A and B, sorted in increasing order, find the minimum value of |A[i]-B[j]| for all i belonging to A and all j belonging to B. Preffered order O(M+n) in the worst case. m being size of array A and n being size of array B.
the same question to n sorted arrays with k elements each, required to find the minimum range in which the values fall.
Title: Re: Array
Post by sateesp on Jul 28th, 2010, 8:17pm

Code:
int value(int a[],int b[])
{
i=1;j=1;
mindiff = a[m]+b[n];
int xi = -1;
int yi =-1;
while(i<=m && j<=n)
{
if ( moduls(a[i]-b[j])< mindiff)
{
mindiff = moduls(a[i]-b[j]);
xi = i;
yi = j;
}

if ( a[i]> b[j])
{
j++;
}
else
{
i++;
}
}
mindiff= contains the |x[i]-y[j]|
}
Title: Re: Array
Post by birbal on Nov 15th, 2010, 1:13am

on 07/28/10 at 20:17:31, sateesp wrote:

Code:
int value(int a[],int b[])
{
i=1;j=1;
mindiff = a[m]+b[n];
int xi = -1;
int yi =-1;
while(i<=m && j<=n)
{
if ( moduls(a[i]-b[j])< mindiff)
{
mindiff = moduls(a[i]-b[j]);
xi = i;
yi = j;
}

if ( a[i]> b[j])
{
j++;
}
else
{
i++;
}
}
mindiff= contains the |x[i]-y[j]|
}


In intialization, mindiff should be
mindiff = moduls(a[m]-b[n]);
Title: Re: Array (find min of |A[i]-B[j]|)
Post by towr on Nov 18th, 2010, 7:14am
This basically comes down to merging, and checking for the smallest difference between consecutive elements (as long as they are from different arrays). So for multiple arrays, you could do it in O(k log (n)) runtime, by using a tree of merging streams, and noting the smallest difference you encounter at any node of that tree. (You'll never have elements from the same array arrive at a node at the same time, so there is no worry you'll note an in-array difference.)
Title: Re: Array (find min of |A[i]-B[j]|)
Post by birbal on Nov 20th, 2010, 10:36pm

on 11/18/10 at 07:14:15, towr wrote:
This basically comes down to merging, and checking for the smallest difference between consecutive elements (as long as they are from different arrays). So for multiple arrays, you could do it in O(k log (n)) runtime, by using a tree of merging streams, and noting the smallest difference you encounter at any node of that tree. (You'll never have elements from the same array arrive at a node at the same time, so there is no worry you'll note an in-array difference.)

What is k n what is n here :|
Title: Re: Array (find min of |A[i]-B[j]|)
Post by towr on Nov 21st, 2010, 1:36am
Same as in the last line of the opening post, n is the number of arrays, k is the number of elements per array.
O(log(n)) is the depth of the tree for merging the arrays.
Title: Re: Array (find min of |A[i]-B[j]|)
Post by Hippo on Dec 8th, 2010, 7:22am

on 11/18/10 at 07:14:15, towr wrote:
This basically comes down to merging, and checking for the smallest difference between consecutive elements (as long as they are from different arrays). So for multiple arrays, you could do it in O(k log (n)) runtime, by using a tree of merging streams, and noting the smallest difference you encounter at any node of that tree. (You'll never have elements from the same array arrive at a node at the same time, so there is no worry you'll note an in-array difference.)


Actually you don't need to sort the entire set to find the answer. I am not sure if I need the log(n) factor.
Basically you can find maximal first element and move through arrays to the last position at most this maximal value. The difference between the maximum and minimal obtained value is the first estimate. (So far so good with O(n) initialisation.)
Now we can move further in array with minimal current value. This gives us new maximal value. We can move in an array to the last element smaller than new maximum, but if the difference is bigger than current estimate, we can made one more step creating new maximum. ...

Actually this algorithm would be worse in the case we could not move in arrays as each array is accessed to find this. And we actually did finding minimum in O(n) time. But may be we could organize the stop elements (first higher in array than current max) better.
Title: Re: Array (find min of |A[i]-B[j]|)
Post by blackJack on Feb 16th, 2011, 8:22am

Quote:
So for multiple arrays, you could do it in O(k log (n)) runtime, by using a tree of merging streams, and noting the smallest difference you encounter at any node of that tree

@Towr, will the complexity not be O(k*n*log(n)) ? As kn will be the total elements in the arrays which we have to see atlast, and taking out an element in sorted fashion from all elements will take O(log(n)) time. Or have i understood it wrong?
Title: Re: Array (find min of |A[i]-B[j]|)
Post by towr on Feb 16th, 2011, 8:51am
I think you're right, I seem to have made an error there.
Title: Re: Array (find min of |A[i]-B[j]|)
Post by wiley on Sep 17th, 2011, 1:37am
@towr.. could you please explain your solution for n arrays in more detail..
Title: Re: Array (find min of |A[i]-B[j]|)
Post by birbal on Dec 24th, 2011, 9:58am

on 12/08/10 at 07:22:48, Hippo wrote:
Actually you don't need to sort the entire set to find the answer. I am not sure if I need the log(n) factor.
Basically you can find maximal first element and move through arrays to the last position at most this maximal value. The difference between the maximum and minimal obtained value is the first estimate. (So far so good with O(n) initialisation.)
Now we can move further in array with minimal current value. This gives us new maximal value. We can move in an array to the last element smaller than new maximum, but if the difference is bigger than current estimate, we can made one more step creating new maximum. ...

Actually this algorithm would be worse in the case we could not move in arrays as each array is accessed to find this. And we actually did finding minimum in O(n) time. But may be we could organize the stop elements (first higher in array than current max) better.


Can you explain your solution stepwise, what exactly are we doing and how are we avoiding logn factor ?
Title: Re: Array
Post by ashmish2 on Mar 22nd, 2012, 3:54am

on 11/15/10 at 01:13:52, birbal wrote:
In intialization, mindiff should be
mindiff = moduls(a[m]-b[n]);


Does it really matter what mindiff is initially , it just has to a greater or equal to max( a[m], a[n]). Right?


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board