Find kthsmallest element from two sorted arrays

Question

I have implemented a working function that does it. But it is not very efficient because it copies a new copy in each call. I am having trouble converting it to using only a_start, a_end, b_start, b_end. I have tried a couple of ways to convert it, but none of them are working for all cases. How can I convert it so that it takes in a start and end pointers for both array a and b? I have tried the following and modified k-i-1 and k-j-1 so that it only takes in k, but did not work.

int m = a_right-a_left, n=b_right-b_left;
int i = (a_left+a_right)/2;
or int i = (int)((m* (k-1)) / (m+n) ); 

Below is my working code using a new copy of array each call.

public static int kthSmallest(int[] a, int[] b,  int k) {
    if (a.length==0)
        return b[k-1];
    else if (b.length==0)
        return a[k-1];
    else if (b.length<a.length)
        return kthSmallest(b, a, k);

        // make sure i + j = k - 1
        int m = a.length, n=b.length;
        int i = (int)((double)m / (m+n) * (k-1));  // make sure i won't be out of bounds
        int j = k - 1 - i;
        int bj_1 = 0, ai_1 = 0;

        if (i==0) {  ai_1 = Integer.MIN_VALUE; } // in case i = 0, outOfBound
        else {  ai_1 = a[i-1]; }
        if (j==0) { bj_1 = Integer.MIN_VALUE; } // in case j = 0, outOfBound
        else {  bj_1 = b[j-1]; }

        if (bj_1 < a[i] && a[i] < b[j]) // kth smallest found, b[j-1] < a[i] < b[j]
            return a[i];
        if (ai_1 < b[j] && b[j] < a[i]) // kth smallest found, a[i-1] < b[j] < a[i]
            return b[j];

        if ( a[i] < b[j] ) // if true, exclude a's lower bound (if 2 arrays merged, a's lower bound must
            // reside before kth smallest, so also update k. 
            // also exclude b's upper bound, since they are all greater than kth element.
            return kthSmallest(Arrays.copyOfRange(a, i+1, a.length), Arrays.copyOfRange(b, 0, j), k-i-1);
        else
            return kthSmallest(Arrays.copyOfRange(a, 0, i), Arrays.copyOfRange(b, j+1, b.length), k-j-1);
}

Answer 1

Here's O(log a.length + log b.length) algorithm from the answer to "How to find the kth smallest element in the union of two sorted arrays?" question. It is a direct port from C++ recursive implementation to Java:

public static int ksmallest(int[] a, int[] b,
                            int a1, int a2, int b1, int b2,
                            int k) {
    int lena = a2 - a1;
    int lenb = b2 - b1;
    assert (0 <= k && k < (lena + lenb));
    if (lena == 0) {
        return b[b1 + k];
    }
    if (lenb == 0) {
        return a[a1 + k];
    }
    int mida = lena / 2;
    int midb = lenb / 2;
    int ma = a[a1 + mida];
    int mb = b[b1 + midb];
    if ((mida + midb) < k) {
        return (mb < ma) ?
            ksmallest(a, b, a1, a2, b1 + midb + 1, b2, k - (midb + 1)) :
            ksmallest(a, b, a1 + mida + 1, a2, b1, b2, k - (mida + 1));
    }
    else {
        return (mb < ma) ?
            ksmallest(a, b, a1, a1 + mida, b1, b2, k) :
            ksmallest(a, b, a1, a2, b1, b1 + midb, k);
    }
}

There is also C++ iterative implementation with the same time complexity (without recursion). It could be ported to Java the same way as the recursive version.

Sanity check for the recursive version:

/** concatenate a, b arrays */
public static int[] concatenate(int[] a, int[] b) {
    int lena = a.length;
    int lenb = b.length;
    int[] c = new int[lena + lenb];
    System.arraycopy(a, 0, c, 0, lena);
    System.arraycopy(b, 0, c, lena, lenb);
    return c;
}

public static void main(String[] args) {
    int a[] = {0, 3, 7, 8};
    int b[] = {0, 2, 3};
    int c[] = concatenate(a, b);
    Arrays.sort(c);
    for (int n = 0; n < (a.length + b.length); n++) {
        int k = ksmallest(a, b, 0, a.length, 0, b.length, n);
        if (k != c[n]) {
            System.out.println(n + ": expected " + c[n] + " got " + k);
        }
    }
}

On success, it prints nothing.

Answer 2

An algorithm with O(n) but simple to understand;

//both arrays are sorted
private int getKthSmallestElement(int[] array1, int[] array2, int k) {
    int elem=-1;
    int index1=0,index2=0;
    while(k != 0 && (index1<array1.length) && (index2 < array2.length))
    {            
        if(array1[index1] < array2[index2])
        {
            index1++;
        }
        else
            index2++;
        k--;         
    }

    if((index1<array1.length) && (index2 < array2.length))
        return array1[index1] > array2[index2] ? array2[index2] :array1[index1] ;
    else
    {
        if(index1 >= array1.length)
        {
            return array2[index2+k]; 
        }
        else{
            return array1[index1+k];            
        }
    }
}

Answer 3

Here is a O((logn)^2) simple recursive solution without copying :-

public class KthElement {
    public static int binSearch(int[] arr,int low,int high,int key) {
        int mid=0;
        while(high>=low) {
            mid = (high+low)/2;
            if(arr[mid]==key) {
                return(mid);
            }
            else if(arr[mid]<key) {
                low = mid+1;
            }
            else {
                high = mid-1;
            }
        }
        if(arr[mid]>key) {
            return(mid-1);
        }
        return(mid);
    }

    public static int kthElement(int[] arr1,int[] arr2,int s1,int h1,int s2,int h2,int k) {
        int len1 = (h1-s1+1);
        int len2 = (h2-s2+1);
        if(len1<=0) {
            return(arr2[s2+k-1]);
        }
        if(len2<=0) {
            return(arr1[s1+k-1]);
        }

        if(k>(len1+len2)) {
            return(-1);
        }

        int mid = (s1+h1)/2;
        int i = binSearch(arr2,s2,h2,arr1[mid]);
        int size = mid+i-s1-s2+2;
        //System.out.println(mid+" "+i+" "+size);
        if(size==k){
            return(arr1[mid]);
        }
        if(size>k) {
            return(kthElement(arr1, arr2, s1,mid-1, s2,i, k));
        }
        else {
            return(kthElement(arr1, arr2, mid+1,h1,i+1,h2, k-size));
        }

    } 

    public static void main(String[] args) {
        int[] arr1 = {1,3,5,7,9,11,13};
        int[] arr2 = {2,4,6,8,10,12};
        int k = 6;
        System.out.println(k+"th Element : "+kthElement(arr1, arr2,0,arr1.length-1, 0,arr2.length-1, k));
    }

}

Answer 4

Here is JAVA iterative solution :

O( log A.length + log B.length ) time complexity

public static int kthsmallest(int []A, int []B, int K){

    int begin = Math.max(0,K-B.length); // binary search begin index
    int end   = Math.min(A.length,K);  // binary search end end index

    while(begin < end){
        // search until mid = k
        int mid = begin +(end-begin)/2;

        if(mid<A.length && K-mid>0 && A[mid]<B[K-mid-1]){
            begin = mid+1;

        }else if( mid > 0 && K-mid <B.length && A[mid-1]>B[K-mid]){
            end = mid;

        }else{
            begin=mid;
            break;
        }
    }

    if(begin ==0){
        return B[K-1];
    }else if(begin == K){
        return A[K-1];
    }else{
        return Math.max(A[begin -1],B[K-begin-1]);
    }
}

Answer 5

Same logic as mentioned in the question, but changed it a little bit to not create new arrays for every call.

//alow, ahigh are used to maintain the size of a array we are using instead 
//of creating a new array. imilarly for blow, bhigh
public static int search(int[] a, int[] b, int alow, int ahigh, int blow, int bhigh, int k){

    if (alow>ahigh) // if "a" array is of zero length, then take kth element from "b"
        return b[blow+k-1];
    else if (blow>bhigh || bhigh-blow == 0) // Similarly, // if "b" array is of zero length, then take kth element from "a"
        return a[alow+k-1];
    else if ((bhigh-blow)<(ahigh-alow)) //always make sure that a's length is lower length
        return search(b, a,blow,bhigh,alow,ahigh, k);

        // make sure i + j = k - 1
        int m = ahigh-alow+1, n=bhigh-blow+1;
        int i = (int)((double)m / (m+n) * (k-1));  // make sure i won't be out of bounds
        int j = Math.min(k - 1 - i,n-1);
        int bj_1 = 0, ai_1 = 0;

        if (i==0) {  ai_1 = Integer.MIN_VALUE; } // in case i = 0, outOfBound
        else {  ai_1 = a[i-1]; }
        if (j==0) { bj_1 = Integer.MIN_VALUE; } // in case j = 0, outOfBound
        else {  bj_1 = b[j-1]; }

        if (bj_1 < a[i] && a[i] < b[j]) // kth smallest found, b[j-1] < a[i] < b[j]
            return a[i];
        if (ai_1 < b[j] && b[j] < a[i]) // kth smallest found, a[i-1] < b[j] < a[i]
            return b[j];

        if ( a[i] < b[j] ) // if true, exclude a's lower bound (if 2 arrays merged, a's lower bound must
            // reside before kth smallest, so also update k. 
            // also exclude b's upper bound, since they are all greater than kth element.
            return search(a, b,alow+i+1,ahigh,   blow,j-1,         k-i-1);
        else
            return search(a,b,alow,  i-1,        blow+j+1,bhigh,   k-j-1);
    }