Find kth Smallest Element in Two Sorted Arrays

O(m+n) Solution:
merge the two arrays using O(m+n) time and space, and then pick kth element from merged array.

O(k) Solution:
using two pointers and a counter, move forward the smaller value one until they are equal or hit k, when they are equal, move both of them forward and count it as 2. This is a solution always came up to me.

O(lgn+lgm) Solution:
I could not figure it out, I could understand many of the explainations but still could not easily to understand the code developed for it. Until I found explain from here:

This is the one finally makes me easily understand how it works.

When you calculate out the position of median, this is also a function to help find the median efficiently form two sorted arrays.

Ideas:
1. try to find half of k from both arrays.
2. compare the k/2th elements, discard the part that is higher than the bigger element in corresponding array, discard the part that is lower than the smaller element in the corresponding array.
3. after step 2, we know the elements smaller than smaller elements are part of the i or j elements within the k smallest elements
4. recursively check the rest of elements for k-i or k-j th smallest element.

First version:

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 33 34 35 36 37 38 39 40 41 42

int findKthSmallestElement(int a[], int b[], int k) { if (a.length > b.length) return findKthSmallestElement(b, a, k);// this is for next condition // check. /* * Now case when size of smaller array is 0 i.e there is no element in * one array */ if (a.length == 0 && b.length > 0) return b[k - 1]; // due to zero based index /* case where K ==1 that means we have hit limit */ if (k == 1) return Math.min(a[0], b[0]); /* Now the divide and conquer part */ //i and j means length and not index int i = Math.min(k / 2,a.length);// Math.min(sizeA, k/2) ; int j = Math.min(k -i,b.length);// Math.min(sizeB, k/2) ; int[] aTmp, bTmp; if (a[i - 1] > b[j - 1]) { // let's use non-smart way the first aTmp = new int[i]; System.arraycopy(a, 0, aTmp, 0, i); bTmp = new int[b.length - j]; System.arraycopy(b, j, bTmp, 0, b.length - j); // Now we need to find only K-j th element since we have found out // the lowest j return findKthSmallestElement(aTmp, bTmp, k - j); } else { aTmp = new int[a.length - i]; System.arraycopy(a, i, aTmp, 0, a.length - i); bTmp = new int[j]; System.arraycopy(b, 0, bTmp, 0, j); // Now we need to find only K-i th element since we have found out // the lowest i return findKthSmallestElement(aTmp, bTmp, k - i); } }

Easy to understand, but not space wise.

Second Version:
In-place algorithm based on first version

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 33 34 35 36 37 38 39 40

static int findKthSmallestElementInPlace(int a[], int b[], int aStart,int aEnd,int bStart, int bEnd,int k) { /* * to maintain uniformity, we will assume that size_a is smaller than * size_b else we will swap array in call :) */ int aLength =aEnd-aStart+1; int bLength = bEnd-bStart+1; if ( aLength > bLength) return findKthSmallestElementInPlace(b, a, bStart,bEnd,aStart,aEnd, k);// this is for next condition // check. /* * Now case when size of smaller array is 0 i.e there is no element in * one array */ if ((aLength == 0 )&& bLength > 0) return b[bStart+k - 1]; // due to zero based index /* case where K ==1 that means we have hit limit */ if (k == 1) return Math.min(a[aStart], b[bStart]); /* Now the divide and conquer part */ int i = Math.min(k/2,a.length);// represents how many steps to advance based on start int j = k -i;// Math.min(sizeB, k/2) ; if (a[aStart+i-1 ] > b[bStart+j-1 ]) { // Now we need to find only K-j th element since we have found out // the lowest j int aS = aStart,aE = aStart+i-1;// including the bigger element int bS = bStart+j,bE = bEnd;//not including smaller element return findKthSmallestElementInPlace(a, b, aS, aE, bS, bE, k-j); } else { // Now we need to find only K-i th element since we have found out // the lowest i int aS = aStart+i,aE = aEnd; int bS = bStart,bE = bStart+j-1; return findKthSmallestElementInPlace(a, b, aS, aE, bS, bE, k-i); } }

Related use:
Find median from two sorted arrays.

1 2 3 4 5 6 7 8

static double findMedian(int a[],int b[]){ int len = a.length+b.length; if(len%2==0){ return (double) ((findKthSmallestElement(a, b, len/2)+findKthSmallestElement(a, b, len/2+1))/2.0); } else return (double) findKthSmallestElement(a, b, len/2+1); }