Kth Element of Two Sorted Arrays
Two sorted arrays; return the k-th smallest of their union in logarithmic time.
- 1 <= m, n <= 10⁵
- 1 <= k <= m + n
- Both arrays are sorted ascending
Intuition
The kth element of two sorted arrays problem wants the k-th smallest value of the union, in logarithmic time. Merging until you reach position k is O(k), which is too slow when k is large.
The reframing is to stop merging and start partitioning. The k smallest values of the union are made up of some prefix of A and some prefix of B — say i from A and k − i from B. Every choice of i gives a candidate split, and exactly one of them is correct.
What makes a split correct? The k elements taken must all be smaller than everything left behind, which reduces to two comparisons across the cut:
- A[i−1] ≤ B[k−i] — the last element taken from A is no larger than the first left in B.
- B[k−i−1] ≤ A[i] — and symmetrically.
When both hold, the k-th smallest is max(A[i−1], B[k−i−1]): the larger of the two elements sitting immediately left of the cut.
Validity is monotone in i, which is what licenses binary search. If A[i−1] is too large, then taking even more from A only makes it worse, so search lower. Binary search on the shorter array to keep the range small, giving O(log min(n, m)).
Out-of-range neighbours are treated as ±∞ so the comparisons work without special cases when a prefix is empty or consumes an entire array.
Median-of-two-sorted-arrays generalised: binary search the partition so that exactly k elements fall on the left. The bounds max(0, k - m) and min(k, n) matter — they keep j = k - i inside the second array. Searching a partition point rather than a value is the transferable move.
Approach
Before reading on: price up what the direct approach costs here, then ask what property lets you throw away half the range after one comparison. Aim for O(log min(n, m, k)) time and O(1) space.
Partition instead of merging
Take i elements from A and k - i from B so that together they are the k smallest. The answer sits immediately left of the cut, so no element-by-element walk is needed once the right split is found.
Write the validity condition
A split is valid when A[i-1] <= B[k-i] and B[k-i-1] <= A[i]. Both must hold: each says that nothing left behind on one side is smaller than something taken from the other.
Use infinities for missing neighbours
When a prefix is empty or takes an entire array, one of those four indices is out of range. Treat a missing left neighbour as −∞ and a missing right neighbour as +∞ — the comparisons then work unchanged, and the alternative is four fiddly special cases.
Binary search on the count from A
Search i in the range [max(0, k - m), min(k, n)], which excludes splits that would need more elements than an array holds. If A[i-1] is too large, reduce i; if B[k-i-1] is too large, increase it.
Search the shorter array
Binary searching the smaller array bounds the iterations at O(log min(n, m)). Swapping the arrays when A is longer costs nothing and keeps the range tight.
Read the answer from the cut
With a valid split, the k-th smallest is max(A[i-1], B[k-i-1]) — the larger of the two values just inside the cut. It is the largest of the k taken, which is exactly the k-th smallest overall.
Cost of the search
O(log min(n, m)) time and O(1) space, against O(k) for merging. This is the same machinery as Median of Two Sorted Arrays, which is this problem with k fixed at the midpoint.
Solution & live demo
Common pitfalls
Merging until the k-th element
merged = sorted(a + b) return merged[k - 1]
i = (lo + hi) // 2 j = k - i
O((n + m) log(n + m)) to read one element. Binary searching the split touches only the four values straddling it, giving O(log min(n, m)).
Using 0 and n as the search bounds
lo, hi = 0, n
lo, hi = max(0, k - m), min(k, n)
j = k - i must be a legal index into b. If k exceeds m, taking too few from a pushes j past the end of b; the tightened bounds make every probe valid without extra guards.
Binary searching the longer array
# no swap n, m = len(a), len(b)
if len(a) > len(b): a, b = b, a
Complexity is O(log min(n, m)) only when you search the shorter side, and the bound arithmetic assumes it. Swapping up front costs nothing and keeps both properties.
Edge cases
Lower bound max(0, k−m) forces enough elements from the other array.
Valid split takes i=2, j=0; sentinels ±∞ make the checks pass.