Kth Element of Two Sorted Arrays

Problem

Return the k-th smallest element (1-indexed) of two sorted arrays a and b in O(log(min(len(a), len(b)))) time.

Binary search a partition of the shorter array such that the left parts together hold k elements and every left value is at most every right value. Sentinels handle empty partitions.

Hint

Partitioning the shorter array fixes the partition of the longer one because together they must hold k elements.

Test cases

case 1

in: [[1,3],[2],2]

expected: 2

case 2

in: [[1,2],[3,4],3]

expected: 3

case 3

in: [[],[1],1]

expected: 1

case 4

in: [[0,0],[0,0],4]

expected: 0

case 5

in: [[2],[],1]

expected: 2

Starter codePython

def kth_two_sorted_arrays(a, b, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor