K-th Smallest Element of Two Sorted Arrays

Reported in interviews at Citadel Hudson River Trading

Problem statement

You are given two sorted arrays $A$ (length $m$) and $B$ (length $n$), sorted in non-decreasing order. Your task is to find the $k$-th smallest element of the combined multiset $A \cup B$ (counting duplicates), for any valid $1 \leq k \leq m + n$.

The brute-force merge is $O(m + n)$ -- too slow when both arrays are large. Design an algorithm that runs in $O(\log \min\{m, n\})$ time and $O(1)$ extra space.

  1. Describe your algorithm and the key binary search invariant that ensures correctness.
  2. Write a clean implementation.
  3. Handle edge cases explicitly: empty arrays, $k = 1$, $k = m + n$, and duplicate elements across arrays.
  4. Argue why the invariant is maintained at each search step and why the algorithm terminates.

Example

find_kth_smallest([5], [5], 2) -> 5
Show hint

Rather than merging, can you describe the $k$ smallest elements by how many of them come from each array?

Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.

Related free problems