K-th element of two Arrays

JavaView on GFG

Intuition

Find kth element in the merged sorted sequence of two sorted arrays. Binary search.

Algorithm

1Binary search: partition arr1 to have i elements and arr2 to have k-i elements. Adjust based on boundary comparisons.

Common Pitfalls

•Same idea as LC 4 (median of two sorted arrays). O(log(min(m,n))). Handle edge cases for array boundaries.

K-th element of two Arrays.java

Java

// Approach: Binary search. Eliminate k/2 elements from one array per step depending on comparison.
// Time: O(log k) Space: O(1)
class Solution {
    public long kthElement(int k, int arr1[], int arr2[]) {
        int n = arr1.length;
        int m = arr2.length;

        if (n > m)
            kthElement(k, arr2, arr1);

        int low = Math.max(0, k - m), high = Math.min(n, k);

        while (low <= high) {
            int cut1 = (low + high) / 2;
            int cut2 = k - cut1;

            int l1 = cut1 == 0 ? Integer.MIN_VALUE : arr1[cut1 - 1];
            int l2 = cut2 == 0 ? Integer.MIN_VALUE : arr2[cut2 - 1];

            int r1 = cut1 == n ? Integer.MAX_VALUE : arr1[cut1];
            int r2 = cut2 == m ? Integer.MAX_VALUE : arr2[cut2];

            if (l1 <= r2 && l2 <= r1)
                return Math.max(l1, l2);
            else if (l1 > l2)
                high = cut1 - 1;
            else
                low = cut1 + 1;
        }

        return 1;
    }
}

Was this solution helpful?