Find the k-th Smallest Element in the Union of Two Sorted Arrays
January 27, 2011 in binary search
Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.
Thanks to an anonymous reader who posted this question.
I would have to admit that this problem is pretty tricky to solve. Like most difficult problems, it requires some pretty clever observations to solve in a neat way.
The trivial way, O(m+n):
Merge both arrays and the k-th smallest element could be accessed directly. Merging would require extra space of O(m+n). The linear run time is pretty good, but could we improve it even further?
A better way, O(k):
There is an improvement from the above method, thanks to readers who suggested this. (See comments below by Martin for an implementation). Using two pointers, you can traverse both arrays without actually merging them, thus without the extra space. Both pointers are initialized to point to head of A and B respectively, and the pointer that has the larger smaller (thanks to a reader for this correction) of the two is incremented one step. The k-th smallest is obtained by traversing a total of k steps. This algorithm is very similar to finding intersection of two sorted arrays.
The best solution, but non-trivial, O(lg m + lg n):
Although the above solution is an improvement both in run time and space complexity, it only works well for small values of k, and thus is still in linear run time. Could we improve the run time further?
The above logarithmic complexity gives us one important hint. Binary search is a great example of achieving logarithmic complexity by halving its search space in each iteration. Therefore, to achieve the complexity of O(lg m + lg n), we must halved the search space of A and B in each iteration.
We try to approach this tricky problem by comparing middle elements of A and B, which we identify as Ai and Bj. If Ai is between Bj and Bj-1, we have just found the i+j+1 smallest element. Why? Therefore, if we choose i and j such that i+j = k-1, we are able to find the k-th smallest element. This is an important invariant that we must maintain for the correctness of this algorithm.
Summarizing the above,
i + j = k – 1,
If Bj-1 < Ai < Bj, then Ai must be the k-th smallest,
or else if Ai-1 < Bj < Ai, then Bj must be the k-th smallest.
If one of the above conditions are satisfied, we are done. If not, we will use i and j as the pivot index to subdivide the arrays. But how? Which portion should we discard? How about Ai and Bj itself?
We make an observation that when Ai < Bj, then it must be true that Ai < Bj-1. On the other hand, if Bj < Ai, then Bj < Ai-1. Why?
Using the above relationship, it becomes clear that when Ai < Bj, Ai and its lower portion could never be the k-th smallest element. So do Bj and its upper portion. Therefore, we could conveniently discard Ai with its lower portion and Bj with its upper portion.
If you are still not convince why the above argument is true, try drawing blocks representing elements in A and B. Try visualize inserting blocks of A up to Ai in front of Bj-1. You could easily see that no elements in the inserted blocks would ever be the k-th smallest. For the latter, you might want to keep the invariant i + j = k – 1 in mind to reason why Bj and its upper portion could never be the k-th smallest.
On the other hand, the case for Ai > Bj is just the other way around. Easy.
Below is the code and I have inserted lots of assertion (highly recommended programming style by the way) to help you understand the code. Note that the below code is an example of tail recursion, so you could technically convert it to an iterative method in a straightforward manner. However, I would leave it as it is, since this is how I derive the solution and it seemed more natural to be expressed in a recursive manner.
Another side note is regarding the choices of i and j. The below code would subdivide both arrays using its array sizes as weights. The reason is it might be able to guess the k-th element quicker (as long as the A and B is not differed in an extreme way; ie, all elements in A are smaller than B). If you are wondering, yes, you could choose i to be A’s middle. In theory, you could choose any values for i and j as long as the invariant i+j = k-1 is satisfied.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | int findKthSmallest(int A[], int m, int B[], int n, int k) { assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n); int i = (int)((double)m / (m+n) * (k-1)); int j = (k-1) - i; assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n); // invariant: i + j = k-1 // Note: A[-1] = -INF and A[m] = +INF to maintain invariant int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]); int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]); int Ai = ((i == m) ? INT_MAX : A[i]); int Bj = ((j == n) ? INT_MAX : B[j]); if (Bj_1 < Ai && Ai < Bj) return Ai; else if (Ai_1 < Bj && Bj < Ai) return Bj; assert((Ai > Bj && Ai_1 > Bj) || (Ai < Bj && Ai < Bj_1)); // if none of the cases above, then it is either: if (Ai < Bj) // exclude Ai and below portion // exclude Bj and above portion return findKthSmallest(A+i+1, m-i-1, B, j, k-i-1); else /* Bj < Ai */ // exclude Ai and above portion // exclude Bj and below portion return findKthSmallest(A, i, B+j+1, n-j-1, k-j-1); } |
Martin said on January 27, 2011
A much simpler algorithm that is O(k) is this:
int findKthSMallest(int[] A, int[] B, int k) {
int a_offset = 0, b_offset = 0;
if (A.length + B.length < k) return -1;
while (true) {
if (a_offset < A.length) {
while (b_offset == B.length ||
A[a_offset] <= B[b_offset]) {
a_offset++;
if (a_offset + b_offset == k) return A[a_offset];
}
}
if (b_offset < B.length) {
while (a_offset == A.length ||
A[a_offset] >= B[b_offset]) {
b_offset++;
}
if (a_offset + b_offset == k) return B[b_offset];
}
}
}
(btw, would be nice to have <pre/> support in comments).
freedom77 said on December 30, 2012
Won’t work for this case
{1,2,3} {4,5}, 3
simon said on January 27, 2011
Hi 1337coder,
You are a genius.
1.
Two reverse sorted arrays A and B have been given.
such that size of A is m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is taken from B. such that k < m*n
It can be done in O(n*n) but i believe it can be done in a very efficient way. I heard someone say there is a paper from SODA. It's possible to solve it in O(N), however, it requires very complex algorithm. I am wondering if you can come up with an NlogN algorithm first then try O(N). These two problems have been very hot interview problems from Google, however, not many people can solve it very efficiently yet. I believe you can do it after I read many posts on your site.
2.
Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.
raman said on April 6, 2011
#include
using std::cin;;
using std::cout;
int main()
{
int A[]={10,8,5,3,2};
int B[]={9,7,6,4,1};
bool atraverse = true;
int sumToBeatAIndex=0;
int sumToBeatBIndex=1;
int j=1;
int k=0;
int i;
int sumtobeat;
int n=5;
int tempBIndex;
int tempAIndex;
cout<<"("<<B[0]<<","<<A[0]<<") ";
sumtobeat=A[0]+B[1];
for(i=1;isumtobeat)
cout<<"("<<B[k]<<","<<A[j]<<") ";
else
{
sumtobeat=B[k]+A[j];
tempBIndex=k;
tempAIndex=j;
j=sumToBeatAIndex;
k=sumToBeatBIndex;
sumToBeatAIndex=tempAIndex;
sumToBeatBIndex=tempBIndex;
cout<<"("<<B[k]<<","<<A[j]<<") ";
atraverse=!(atraverse);
}
if(atraverse)
j++;
else
k++;
}
cout<<"\n";
return 0;
}
Raynor said on January 27, 2011
I just want to point out that the trivial way does not require that much of space. You don't need to merge two arrays. Just traverse through them is enough.
1337c0d3r said on January 27, 2011
@simon:
1) Using a heap-based solution you could get O(k lg min(m, n)) run time complexity. To figure out the O(n) solution seemed pretty difficult. It seemed like someone already solved it here: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1132204952;start=25
I haven't read his post, so I couldn't provide the validity of his solution yet.
2) I remembered seeing this as an exercise problem in CLRS. Will look into it when I have time.
1337c0d3r said on January 27, 2011
@Martin and Raynor:
Yup both of you are right. I have updated my post, thanks!
Anonymous said on January 28, 2011
@1337 — u are seriously a bilody genius or someone who has spent hours at algos. at work or at school and can tie all the algo concepts really well (Which is really encourage-able)
Now-a-days at most software jobs where you just code (mostly read from a trivial DB and do some business logic and display results) you lose this touch.
Thanks for all the great posts.
1337c0d3r said on January 28, 2011
@Anonymous:
Definitely the latter. I love algos and though I admit it didn't get apply at work very often, it does come into play once in awhile.
Have you read the book "Programming pearls"? It gives some really good real world examples of how efficient algos can help even in some simple business logic.
Anonymous said on January 29, 2011
The following algorithm can achieve O(logK) complexity. The idea is to first select k items from both arrays using their proportional length, then adjust the number of items from each array using binary search. The follwoing C# code illustrates the idea:
private static int FindKthInUnion(int[] a, int[] b, int k)
{
if (k == 0) return Min(a[0], b[0]);
int la = Min(a.Length – 1, k);
int lb = Min(b.Length – 1, k);
int i = (k * a.Length) / (a.Length + b.Length);
int j = k – i – 1;
for (; ; )
{
if (a[i] < b[j])
{
if (i == la || a[i + 1] > b[j])
{
return b[j];
}
else
{
i += (la – i + 1) / 2;
j = k – i – 1;
}
}
else
{
if (j == lb || b[j + 1] > a[i])
{
return a[i];
}
else
{
j += (lb – j + 1) / 2;
i = k – i – 1;
}
}
}
}
Anonymous said on February 7, 2011
Hi 1337coder,
Can you please tel me why "We make an observation that when Ai < Bj, then it must be true that Ai < Bj-1 (you mentioned Bj-1 <Ai < Bj, right?). On the other hand, if Bj < Ai, then Bj < Ai-1." ?
Thank you very much
1337c0d3r said on February 7, 2011
@Anonymous:
If Bj-1 < Ai < Bj, then we are already done, no need to continue further.
"We make an observation that when Ai < Bj, then it must be true that Ai < Bj-1" –> This observation is due to the above condition Bj-1 < Ai < Bj NOT being satisfied.
Anonymous said on February 9, 2011
I found this code sample to be easier to understand:
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s01/recitations/rec03/rec03.ps
anonymous said on April 6, 2011
I can see some limitation in this code. It won’t work if first array is of size 100, second is of size 10, and k = 50. It probably works only when k <= min (first array size, second array size)
Ashok Koyi said on October 31, 2011
I think we can augment the code to skip the steps of comparison, if we knew that the index we have calculated is out of bounds in the smaller array
online.service said on February 14, 2011
Hi 1337code, "Using a heap-based solution you could get O(k lg min(m, n)) run time complexity. " for simon's question 1. I feel we need a O(k lg max(m, n)), since after pop a max in the heap, we need to fill two neighbour items to the heap, we can get a max(m,n) heap for some m*n matrix like this one
3*n matrix
3*(n+n 2*n n
3*(2n-1) 2*(n-1) n-1
.
.
.
3*(n) 2 1
so the largest will be in the first column, after we pop the max in the heap , we need to push the next one in the first column and the one in the same row but in second column. So we get to the end of the first column we have a O(n) space heap
ripper234 said on February 14, 2011
Regarding simon's problems. I went over the discussion at the Berkly forum and didn't find any solution that I was convinced both works and is O(n). I posted this to Stack Overflow, hoping the discussion there will turn out to be more fruitful:
http://stackoverflow.com/questions/5000512/find-the-top-k-values-in-a-sorted-n-x-n-matrix
orchid said on April 25, 2011
int findKthSmallestInoneset(int s1[], int s2[], int m, int n, int k){
int mid, low, high, pos;
if(k > (m + n))
cout << "There does not exist the k-th element" < s2[n - 1])
return s1[m - 1];
else
return s2[n - 1];
}
if(k == 1){
if(s1[0] > s2[0])
return s2[0];
else
return s1[0];
}
if(k > m)
high = m – 1;
else
high = k – 1;
low = 0;
while(low (n – 1)){
low = mid + 1;
continue;
}
if(pos == (n – 1)){
if(s1[mid] >= s2[pos])
return s1[mid];
low = mid + 1;
}
else{
if(s1[mid] >= s2[pos] && s1[mid] = s2[pos + 1])
high = mid – 1;
if (s1[mid] < s2[pos])
low = mid + 1;
}
}//while
return 0;
}
orchid said on April 25, 2011
a non-recrusive method
tanliboy said on May 1, 2011
There is an O(lg(min{m, n, k}) method.
FYI.
http://tanliboy.wordpress.com/2011/05/01/some-interesting-google-interview-problems/
David said on May 16, 2011
I was looking for a solution to a very similar problem, the k-th largest element of 2 vectors sorted in nondecreasing order. I tried to adapt the solution to use with vectors, but it just did’t work:
I just call the “select” function with the 2 vectors and fit them in 2 arrays. I think the algorithm is incorrect.
I did the same with the solution above, from talinboy:
It works perfectly and with O(lg(min{m, n, k}) !!
I don’t know where is the error in your algorithm. It might be i’m also using vectors with duplicate elements.
I think the algorithm from tanliboy is the quickest and most general implementation i’ve seen in internet that works fine.
P.S.: two examples that doesn’t work with 1337 code:
1337c0d3r said on May 16, 2011
David, please read my post carefully:
“You can assume that there are no duplicate elements.”
My solution assumes no duplicate elements. If you really understand how my solution works, you should be able to adapt it to work with duplicate elements. tanliboy’s solution is another possible efficient solution, which uses the idea of binary search.
Anantha Krishnan said on June 16, 2011
#include
int findKthsmallest(int a[],int m,int b[],int n,int k)
{
int i=0,j=0,ti=0,tj=0,I=0,J=0,M=m,N=n;
while(1)
{
ti = (int)((double)m/(m+n) * (k-1));
tj = (k-1)-ti;
i = I+ti;
j= J+tj;
//printf(” i=%d j=%d\n”,i,j);
if(j>0 && j<N && ib[j-1] && a[i]0 && i<M && ja[i-1] && b[j]<a[i])
return b[j];
if(j==0 && i<M && a[i]<b[j])
return a[i];
if(i==0 && j<N && b[j]b[j-1])
return a[i];
if(i==M && b[j]>a[i-1])
return b[j];
if(i<M && j<N)
{
if(a[i]=M)
{
k=k-tj-1;
n=n-tj-1;
J=j+1;
}
else
{
k=k-ti-1;
m=m-ti-1;
I=i+1;
}
}
}
int main()
{
int a[]={1,2,3};
int b[]={4};
int m=3,n=1,k=3;
printf(“%d”,findKthsmallest(a,m,b,n,k));
return 0;
}
daxingqiao said on June 19, 2011
Hi 1337, there is one bug for your solution. How is it going if k = m+n? I think we need special handling for this edge case.
daxingqiao said on June 19, 2011
There is another bug when m == 1 or n == 1, in this case, we need special handling to adjust i or j, here is the code snippet I have modified:
int findKthElement(int A[], int m, int B[], int n, int k)
{
if ( m == 0 && n == 0 || k == 0 || k > m + n)
{
return -1;
}
else if( m == 0)
{
return B[k - 1];
}
else if (n == 0)
{
return A[k - 1];
}
else if(k == m + n)
{
return std::max(A[m - 1], B[n -1]);
}
else if( k == 1)
{
return std::min(A[0], B[0]);
}
int i = (int)(double(m)/(m+n)*(k – 1) + 0.5);
int j = k-1-i;
if (i == m)
{
i–;
j++;
}
else if (j == n)
{
i++;
j–;
}
// A[i-1], B[j-1]
int A_i_1 = ( i == 0)? INT_MIN : A[i - 1];
int B_j_1 = ( j == 0)? INT_MIN : B[j - 1];
if (A[i] >= B_j_1 && A[i] <= B[j])
{
return A[i];
}
else if (A[i] = A_i_1 && B[j] <= A[i])
{
return B[j];
}
else if (B[j] <= A[i])
{
return findKthElement(A, i, B + j + 1, n – j – 1, k – j – 1);
}
return -1;
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if (m + n & 1)
{
return findKthElement(A, m, B, n, (m + n + 1)/2);
}
else
{
return (findKthElement(A, m, B, n, (m + n)/2) + findKthElement(A, m, B, n, (m + n)/2 + 1))*1.0/2;
}
return -1;
}
siva said on June 26, 2011
Can we not do in log k?
have 2 pointers.. i and j for array 1 and array 2..
while (i+j != k) {
if (array1[i] > array2[j]) {
i = i + [(k-(i+j))/2]
} else {
j = j + [(k-(i+j))/2]
}
}
return min of (array[i] , array [j])
validate this one..
Nitish said on June 29, 2011
Siva, initially n=100000, m=10;
suppose k=1000;
i=0;j=0;
arrray1[]={ 1,2,3,4….}
array2[]={100901,1212}’
Now, as array1[i=0] j is set to 10000. Seg fault
siva said on July 2, 2011
you are correct.. I missed to have bound check on both i and j.. if we do that.. we can do this solve this in log k rite?
Anurag Atri said on July 4, 2011
Again , fantastic work , a tried to get a solution to this problem on a lot of places on the net but all of them were either wrong or lacked explanation , your code works fine and the explanation is great !
just one thing , you can include these tests :
m = min ( k , m ) ;
n = min ( k , n ) ;
a slight improvement .
and if you use
if ( ai >= bj_1 && ai <= bj ) //greater than equal to , in place of greater than
the code will work for duplicate values as well ( provided values of i and j are checked )
Thank You sooo much
new said on July 19, 2011
was wondering why you initialized i this way, why not i from 0?
”
int i = (int)((double)m / (m+n) * (k-1));
int j = (k-1) – i;”
maxq said on July 20, 2011
I just wrote another version with the same log complexity,
and verified with a few inputs via your coding panel:)
Any comments?
// Type your C++ code and click the “Run Code” button!
// Your code output will be shown on the left.
// Click on the “Show input” button to start entering input data.
#include
using namespace std;
int find_k_small(int a[], int m, int b[], int n, int k, int &kmin)
{
if (k m+n)
return -1;
int i = (m * (k-1))/(m+n);
int j = k – 2 – i;
while (1) {
if ((j == n-1 || a[i] < b[j+1]) &&
(i == m-1 || b[j] b[j]) ? a[i]: b[j];
return 1;
} else if (j = b[j+1]) {
i /= 2;
j = k -2 -i;
} else {
j /= 2;
i = k -2 -j;
}
}
return 0;
}
int main() {
// Start typing your code here…
int kmin = 0;
int a[] = {1,3, 9, 11, 13, 15, 23};
int b[] = {2, 4, 6, 16, 18, 20};
int ret = find_k_small(a, sizeof(a)/sizeof(int),
b, sizeof(b)/sizeof(int),
9, kmin);
cout <<"ret="<<ret<<",kmin="<<kmin<<endl;
return 0;
}
Coder said on July 30, 2011
Are both arrays sorted in increasing order or decreasing order….
if they are sorted in increasing order ,How is this claim true??
We make an observation that when Ai < Bj, then it must be true that Ai < Bj-1. On the other hand, if Bj < Ai, then Bj < Ai-1.
i may sound stupid but i dont get this claim
lipingwu said on August 7, 2011
The i and j are not the middle of the array, then how can you prove that the algorithm will be O(lgm + lgn) or less? Thanks.
siv said on September 28, 2011
Hi,
Can some one explain me why ‘i’ value is calculated as below
int i = (int)((double)m / (m+n) * (k-1));
Thanks,
siv
ibrahim said on February 1, 2013
that’s for to stay inside of the array. if m < (k-1) /2 i will be out of array bounds
japanbest said on October 13, 2011
why set the ratio i/j= m/n , I prefer i=j, in other words, i=j= (k-1)/2
Since the next recursion k-> k-i or k->k-j if i=j then we can optimize for the worst case. And yes I know both ratios work the same in average cases.
Does i/j=m/n has a special objective?
ibrahim said on February 1, 2013
that’s for to stay inside of the array. if m < (k-1) /2 i will be out of array bounds
Jeffrey said on December 30, 2011
The post says
I don’t agree. If A is [1,2,3], B is [4,5,6], then this statement is not true.
idank said on January 20, 2012
I solved this using a similar approach in O(lgn), see here for an explanation.
reader said on March 4, 2012
Hi 1337c0d3r.
I am having trouble understanding your code.
1) You mention that the k is found if Bj-1 < Ai < Bj AND the invariant i+j+1==k holds true.
But I don’t see how you check for the invariant in your code.
You just return if for the current i,j the condition Bj-1 < Ai < Bj (or its reverse for B) holds true.How do you check for the invariant?
2) Also your code does not do what you describe in the code.If Ai<Bj you do a recursive call and you use j as the size of the array.So you just don't neglect a portion as you say.
3)For A={1,2,6} and B={3,4,5} and k = 2, the code ends up with division by 0 when calculating i since in the first entry of the method i=0 and j=1 and so you dont' find k and you hit the Ai<Bj and you call the method recursevily with k-i-1 which is 2-0-1=1 so in the calculation of i you divide by zero.
This is a very interesting problem and perhaps I didn't get your solution, so if you please took the time to read my comments and help me understand this I would be greatful. Thank you
upi said on March 26, 2012
Narrow bounding method.
Assume we have two arrays A (A.size() == n) and B (B.size() == m) and k – target value.
In case of n<=0 or m= 1.
Get median element of A (A[n/2]) and find position in B, where we can insert such element, let position be i, such that:
- i==0 and B[i] > A[n/2];
- i==m and B[i-1] < A[n/2];
- 0 < i < m and B[i-1] < A[n/2] k, then we start procedure with A[0..n/2-1], B[0..i-1]
3. i+n/2+1 < k, then we start procedure with A[n/2+1..n-1], B[i+1..m-1], k -= i+n/2+1
try to code:
Is it correct?
upi said on March 26, 2012
Strange code formatting:
/// Assume k start from 1
int findKth (int *A, int n, int *B, int m, int k)
{
/// trivial border case (don’t forget k started from 1)
if (n <= 0) return B[k-1];
if (m k)
{
return findKth (A, n/2, B, i, k);
}
return findKth (&A[n/2+1], n – n/2 -1, &B[i], m – i, k – (i + n/2 + 1));
}
veeru said on March 31, 2012
if (k >= s1.Length + s2.Length)
throw new ArgumentOutOfRangeException(“k”);
while(i s2.Length)
{
break;
}
if (i + j + 1 == k)
break;
if (s1[i] < s2[j])
i++;
else
{
j++;
}
}
if(i == s1.Length)
{
while (i + j + 1 != k)
j++;
return s2[j];
}
if(j == s2.Length)
{
while (i + j + 1 != k)
i++;
return s1[i];
}
if(i + j + 1 == k)
{
return s1[i] <= s2[j]?s1[i]:s2[j];
}
return int.MaxValue;
}
jastination said on April 23, 2012
Hi Genius!
What if arrays are unsorted? Do you have a good solution for that?
Thanks!
vk said on May 12, 2012
i found martin’s explanation slightly off …what if there are duplicates
thus i implemented the same concept( using 2 ptrs )which actually worked for me and it handles duplication as well…cheers
int kthsmallest(int *A,int *B,int k)
{
int i=0,j=0;
k=k-1;
while(1)
{
if(A[i]B[j])
{ if(i+j==k)return B[j];
j++;
}
else //(A[i]==B[j])
{if(i+j==k)return A[i];
i++;j++;k++;
}
}
}
flynewdream said on May 16, 2012
Why “We make an observation that when Ai < Bj, then it must be true that Ai < Bj-1. On the other hand, if Bj < Ai, then Bj < Ai-1" ?
Ai can be between Bj and Bj-1, right?
Hai said on July 3, 2012
then you found the solution.
Fred said on May 22, 2012
actually, we can initially bound m and n to be smaller than k.
m=min(m,k);
n= min(n,k);
then the time complexity is O(log(k))
Hai said on July 3, 2012
Seems original code can not handle the case if A and B doesn’t overlap, e.g:
A= {2 , 4} B={ 7, 9, 11, 13}, will has assertion fail.
golden said on August 14, 2012
int first=0,second=0,k,min;
scanf(“%d”,&k);
while((k–) > 0)
{
if (b[second]<a[first])
{ min=b[second];second++;}
else{
min=a[first];
first++;}}
this is working code
Prateek Caire said on August 19, 2012
Thanks
Median of 2 sorted array is special case of this one where k = (m+n)/2
rajat said on September 4, 2012
by comparing middle elements of A and B, which we identify as Ai and Bj. If Ai is between Bj and Bj-1, we have just found the i+j+1 smallest element.
I think instead of Bj-1 it should be Bj+1
imposter said on September 27, 2012
can any one please tell me why pivot i is choosen as m/(m+n)*(k-1) … i didnt get the logic for that…
sankalp said on October 6, 2012
hey I don’t understand why the element is i+j+1 th smallest.
Ai has i-1 elements ahead of it in the original array and j-1 elements in the second array . Thus , it is i+j-1 th element I think.
YangOu said on February 21, 2013
I actually have the same question. Have you figured out?
phantom11 said on March 31, 2013
Here indexing is done 0 based. So Ai has i elements before it and Bj_1 has j elements before it (+1 including it ,so j+1 elemtns less than equal to it). So it is i+j+1
Juanissa said on March 1, 2013
@1337c0d3r, what if the arrays are constant arrays of the same value? I think
if (Bj_1 < Ai && Ai < Bj)
return Ai;
else if (Ai_1 < Bj && Bj < Ai)
return Bj;
can be
if (Bj_1 <= Ai && Ai <= Bj)
return Ai;
else if (Ai_1 <= Bj && Bj <= Ai)
return Bj;
Anonymous said on March 4, 2013
You really should provide the reference where you get these solutions. This article is almost identical to the solution provided in Algorithms for Interviews book, exercise 1.18. It lays the three solutions in the same sequence and with similar explanations.
For the sake of fairness, don’t pretend these are your bright ideas.
However I congratulate you on the quality of the narrative and code examples.
kgiFozzteg said on April 9, 2013
Wholesale Cheap 1:1 replica louis vuitton Handbags / Bags / Purses from china Online Outlet for Sale
http://glennvytf2.webs.com/ lmsbnj
Wholesale Cheap 1:1 replica louis vuitton Handbags / Bags / Purses from china Online Outlet for Sale
zxifxj
Terry Li said on April 11, 2013
log(m+n) solution without recursive:
Terry Li said on April 11, 2013
here it is:
public int findKthLargest(int A[], int B[], int k) {
int n = A.length;
int m = B.length;
if (k m + n)
return -1;
int al = 0, ar = n – 1;
int bl = 0, br = m – 1;
while (true) {
n = ar – al + 1;
m = br – bl + 1;
int i = Math.max(0, (int) ((1.0 * n * (k – 1)) / (m + n)));
int j = k – 1 – i;
i += al;
j += bl;
if (al > ar)
return B[j];
if (bl > br)
return A[i];
int ai = (i > ar) ? Integer.MAX_VALUE : A[i];
int ai_1 = (i br) ? Integer.MAX_VALUE : B[j];
int bj_1 = (j = bj_1 && ai = ai_1 && bj <= ai) {
return bj;
}
if (ai < bj) {
k -= i – al + 1;
al = i + 1;
br = j;
} else {
k -= j – bl + 1;
ar = i;
bl = j + 1;
}
}
}
frank said on May 14, 2013
The author gave a very good point in providing the relationship between i,j and k: i+j = k-1. And I believe the best algorithm should have the time complexity of O(log(min(m,n,k)). Simple proof:
Suppose m>=n,
case 1: k=m, since m+n>=k, we can flip to find the m+n-k’th largest element. and m+n-k<=n. So same as case 1.
case 3: n<k<m,
case 3a: if n = O(k), no problem.
case 3b: if n = o(k), we can use the bisection method for the small array. And it's not hard to find the k's smallest element in O(n).
frank said on May 15, 2013
This is the C# code with time complexity O(min(m, n, k)). All possible cases were covered.
cpthk said on May 15, 2013
Really nice post. But I do have 1 questions.
I am not convienced that 3rd solution O(lg m + lg n) is *always* better than 2nd solution O(k).
I do agree that O(log m) is better than O(m), but I do not agree that O(log m) is *always* better than O(k).
If k = 3, m = 100000, n = 100000
Using the 2nd solution, you would only need to traverse 3 steps to get the answer
Using the 3rd solution, in the worst case, you would need to traverse log(100000) + log(100000).
It is obvious that 3 < log(100000) + log(100000).
In this case, it is obvious that 2nd solution would run faster.
Am I correct?
frank said on May 17, 2013
My algorithm always ensures the time complexity is O(lg(min(m,n,k))).
Assuming m>=n, so there are 3 possibilities:
1. k<=n,
we only consider A[0..k-1] and B[0..k-1]. So it is O(lg(k))
2. n<km
since k smallest is the same as m+n+1-k largest, and value of m+n+1-k is always <= n, Set m+n+1-k = p. We only need to consider the interval A[m-p, m] and B[n-p, n]. And the time complexity is O(lg(p)), i.e., O(lg(n)).
frank said on May 17, 2013
c++ code. It works fine in visual studio, but failed on leetcode because leetcode doesn’t support time class.