K-th element of two Arrays

JavaView on GFG

Problem Overview

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

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?