Author |
Topic: Array (find min of |A[i]-B[j]|) (Read 5060 times) |
|
witee
Newbie
Posts: 48
|
 |
Array (find min of |A[i]-B[j]|)
« on: Jul 28th, 2010, 3:51pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Jul 29th, 2010, 6:19am by Grimbal » |
 IP Logged |
|
|
|
sateesp
Newbie
Gender: 
Posts: 35
|
|
Re: Array
« Reply #1 on: Jul 28th, 2010, 8:17pm » |
Quote Modify
|
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]|
}
|
|
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Array
« Reply #2 on: Nov 15th, 2010, 1:13am » |
Quote Modify
|
on Jul 28th, 2010, 8:17pm, 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]);
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Array (find min of |A[i]-B[j]|)
« Reply #3 on: Nov 18th, 2010, 7:14am » |
Quote Modify
|
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.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Array (find min of |A[i]-B[j]|)
« Reply #4 on: Nov 20th, 2010, 10:36pm » |
Quote Modify
|
on Nov 18th, 2010, 7:14am, 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 :|
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Array (find min of |A[i]-B[j]|)
« Reply #5 on: Nov 21st, 2010, 1:36am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 21st, 2010, 1:41am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Array (find min of |A[i]-B[j]|)
« Reply #6 on: Dec 8th, 2010, 7:22am » |
Quote Modify
|
on Nov 18th, 2010, 7:14am, 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.
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Array (find min of |A[i]-B[j]|)
« Reply #7 on: Feb 16th, 2011, 8:22am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Array (find min of |A[i]-B[j]|)
« Reply #8 on: Feb 16th, 2011, 8:51am » |
Quote Modify
|
I think you're right, I seem to have made an error there.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wiley
Newbie
Posts: 12
|
|
Re: Array (find min of |A[i]-B[j]|)
« Reply #9 on: Sep 17th, 2011, 1:37am » |
Quote Modify
|
@towr.. could you please explain your solution for n arrays in more detail..
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Array (find min of |A[i]-B[j]|)
« Reply #10 on: Dec 24th, 2011, 9:58am » |
Quote Modify
|
on Dec 8th, 2010, 7:22am, 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 ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
ashmish2
Newbie
Posts: 12
|
|
Re: Array
« Reply #11 on: Mar 22nd, 2012, 3:54am » |
Quote Modify
|
on Nov 15th, 2010, 1:13am, 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?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print