Find the kth smallest element in two sorted arrays with complexity of (logn)^2

Question

S and T are two sorted arrays with n elements (integer) each ,describe an algorithm to find the kth smallest number in the union of two arrays(assuming no duplicates) with time complexity of (logn)^2. Note that it is fairly easy to find an algorithm with complexity of logn.

http://stackoverflow.com/questions/4607945/how-to-find-the-kth-smallest-element-in-the-union-of-two-sorted-arrays might help you — User_Targaryen, Oct 05 '16 at 05:55

score 0 · Accepted Answer · answered Oct 05 '16 at 06:02

An optimized O( min( log(k),log(m+n) ) working solution for your problem is pasted below

public class KthSmallestIterative {

    public static int kthSmallest(int[] A, int[] B, int k) {
        if (A == null || B == null) {
            throw new IllegalArgumentException("Arrays cannot be null!");
        }

        int a = A.length;
        int b = B.length;

        if (k < 1 || k > a + b) {
            throw new IllegalArgumentException("k is not within range!");
        }

        int minSizeA = Math.max(0, k - b);
        int maxSizeA = Math.min(a, k);

        while (minSizeA <= maxSizeA) {
            int sizeA = minSizeA + (maxSizeA - minSizeA) / 2;
            int sizeB = k - sizeA;
            int indexA = sizeA - 1;
            int indexB = sizeB - 1;
            int indexANext = syzeA;
            int indexBNext = sizeB;
            int valA = (indexA < 0) ? Integer.MIN_VALUE : A[indexA];
            int valB = (indexB < 0) ? Integer.MIN_VALUE : B[indexB];
            int valANext = (indexANext >= a) ? Integer.MAX_VALUE : A[indexANext];
            int valBNext = (indexBNext >= b) ? Integer.MAX_VALUE: B[indexBNext];

            if (valA <= valBNext && valB <= valANext) {
                return Math.max(valA, valB);
            } else if (valA > valBNext) {
                maxSizeA = sizeA - 1;
            } else {
                minSizeA = sizeA + 1;
            }
        }
    }

    public static void main(String[] args) {
        int[] list1 = new int[] { 3, 4, 10, 23, 45, 55, 56, 58, 60, 65 };
        int[] list2 = new int[] { 3, 3, 3, 15, 16, 28, 50, 70, 71, 72 };
        int k = 13;

        int kthSmallest = kthSmallest(list1, list2, k);
        System.out.println(k + "th smallest is " + kthSmallest);
    }



        return 0;
    }
}

reference

Thanks for reply but I am interested O((logn)^2) algorithm (for the sake of homework assignment) — Ashutosh Singh, Oct 06 '16 at 15:44
@AshutoshSingh, Do you know O(n) is also O(n^2). so this algorithm can be called as O(log(n)^2) as well. — v78, Oct 07 '16 at 04:30

Find the kth smallest element in two sorted arrays with complexity of (logn)^2

1 Answers1