Find the K-th Smallest Value in Two Sorted Arrays

Given two nondecreasing integer arrays and a one-based integer k, return the k-th smallest value in their combined multiset. Duplicates count separately. Do not merge the full arrays.

Function Contract

Implement kth_smallest_two_sorted(a, b, k) -> int.

Constraints

• 0 <= length of each array <= 200000, and at least one array is nonempty.
• 1 <= k <= len(a) + len(b).
• Values are integers between -10^9 and 10^9.
• Expected extra space is O(1), with logarithmic search complexity in the shorter array.

Examples

a = [1, 3, 7], b = [2, 2, 9], k = 4
output = 3

a = [], b = [5], k = 1
output = 5

Hint: Exercise imbalanced inputs

Test an empty array, one array much shorter than the other, duplicate boundary values, and k at both extremes.

Hint: Honor the search bound

Merging until the k-th value can be correct but does not achieve logarithmic complexity in the shorter array.

Find the K-th Smallest Value in Two Sorted Arrays

Hints

1. Test either array empty, one array much shorter, and k at both one-based extremes.
2. Include duplicates equal across the candidate partition boundary.
3. Use negative values and both numeric limits in sorted order.

Approach

Binary-search how many of the first k values come from the shorter array; the rest come from the other array. A partition is valid when both left boundaries are no greater than the opposite right boundaries. If not, move the shorter-array count left or right. At a valid partition, the larger left boundary is the k-th value.

• Time complexity: O(log min(len(a), len(b))) time.
• Space complexity: O(1) auxiliary space.