### Thread: Finding kth largest element in a union of two arrays.

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Apr 2004
Posts
2
Rep Power
0

#### Finding kth largest element in a union of two arrays.

Given two *sorted* arrays of n elements each, is it possible to find the kth smallest element in the union of the arrays in a logarthimic time algorithm? I noticed a similar posting with a single unsorted array (http://forums.devshed.com/t67403/s.html). I do realise that I need to do some sort of binary search, but Im not exactly sure how to begin since I have two arrays and not one.

Anyone had any experience with a similar problem? Thanks.
2. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
London, England
Posts
1,585
Rep Power
1373
If you had a single sorted array A then the kth smallest element would be A[k], a constant time operation. To find the kth smallest element of two sorted arrays you would need to merge the first k elements of the arrays. This can be done in O(k), but not logarithmic time.

Dave - The Developers' Coach
3. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1313
No, DevCoach. Log time is enough. In fact, this problem is amenable to something very similar to binary search. Suppose my arrays are A and B. The idea is to keep track of two indices, a (for A) and b (for B), such that a + b = k - 1 (it's very important to maintain this invariant). It's easy to check whether A[a] or B[b] is the answer: A[a] is the answer if and only if

B[b-1] <= A[a] <= B[b],

and B[b] is the answer if and only if

A[a-1] <= B[b] <= A[a],

where we use the convention that A[-1] = B[-1] = "negative infinity." (This can be determined in constant time.) Moreover, if neither of these is the case, you can divide the problem in half: if A[a] < B[b-1], you restrict your attention to the portion of A above index a and the portion of B below index b, and otherwise (it must be the case that B[b] < A[a-1]), you restrict your attention to the portion of A below index a and the portion of B above index b. (If you start with a and b in the middle of the arrays and always make the new indices be in the middle of the subarrays you're considering at that point, this step will always divide the problem in half.)

I haven't tested that algorithm (I just came up with it), so I can't guarantee that it works, but I guarantee that it will work with at most very slight modifications.
4. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
London, England
Posts
1,585
Rep Power
1373
Originally Posted by Lux Perpetua
No, DevCoach. Log time is enough. In fact, this problem is amenable to something very similar to binary search.
<algorithm snipped>
Yes, you are right. Very neat.

Dave - The Developers' Coach
5. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Apr 2004
Posts
2
Rep Power
0
Lux Perpetua, I'm sorry for the late reply. I only had time to implement the algorithm now. I just wanted to thank you very much for your help. It worked perfectly. I guess the invariant was the point I overlooked.
6. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2010
Posts
1
Rep Power
0
Originally Posted by spikecuz
Lux Perpetua, I'm sorry for the late reply. I only had time to implement the algorithm now. I just wanted to thank you very much for your help. It worked perfectly. I guess the invariant was the point I overlooked.
i am working on this algorithm friend but i didn't got the question very clear >> so could you please explain if we gonna merge the two lists and how