Kth Element of Two Sorted Arrays — Binary Search Elimination

Problem · Kth Element of Two Sorted Arrays

Difficulty: Hard · Pattern: Binary Elimination

Find kth smallest from two sorted arrays without merging.

Intuition

Compare elements at index k//2-1 in both arrays. The array with the smaller element — those first k//2 elements can be safely eliminated (they can't be the kth element).

Solutions

# Python
def findKthElement(A, B, k):
    if not A: return B[k-1]
    if not B: return A[k-1]
    if k == 1: return min(A[0], B[0])
    # Compare k//2 elements
    half = k//2
    a_idx = min(half, len(A))-1
    b_idx = min(half, len(B))-1
    if A[a_idx] <= B[b_idx]:
        return findKthElement(A[a_idx+1:], B, k-a_idx-1)
    else:
        return findKthElement(A, B[b_idx+1:], k-b_idx-1)

// Java
int findKth(int[] A, int i, int[] B, int j, int k) {
    if (i>=A.length) return B[j+k-1];
    if (j>=B.length) return A[i+k-1];
    if (k==1) return Math.min(A[i],B[j]);
    int half=k/2;
    int aVal=i+half-1<A.length?A[i+half-1]:Integer.MAX_VALUE;
    int bVal=j+half-1<B.length?B[j+half-1]:Integer.MAX_VALUE;
    if (aVal<=bVal) return findKth(A,i+half,B,j,k-half);
    return findKth(A,i,B,j+half,k-half);
}

Complexity

Time: O(log k) = O(log(m+n))
Space: O(log k) recursive