The challenge
Return the kth smallest value in two sorted arrays, counting duplicates separately.
k is 1-based and 1 ≤ k ≤ n + m. One array may be empty. Invalid k raises an error.
Example
A = [2, 3, 6, 7, 9], B = [1, 4, 8, 10], k = 5 → 6.
Use the walkthrough below to inspect the input and each state change.
See Kth partition, step by step
Inspect the comparison, the invariant, and the next boundary.
- Left cut bound
- 0
- Cut in A
- —
- Right cut bound
- 4
Search cuts in the shorter array
A has 4 values, B has 5. The combined left side must contain 5 entries.
i ∈ [0, 4]; j = 5 − iRecorded result so far
View exact input
Original A: [2,3,6,7,9] · Original B: [1,4,8,10] · k = 5
The diagram relabels the shorter array A. Cuts count elements on the left; missing boundary values are −∞ or +∞.
Put it into code
Use the same valid-partition test as median, but put exactly k elements on the combined left. The largest left value is the kth element.
Indices are zero-based. C++ uses C++17 or later.
def kth_two_sorted(a, b, k):
# Both arrays sorted; k is 1-based, 1 <= k <= len(a) + len(b).
if len(a) > len(b):
return kth_two_sorted(b, a, k)
n, m = len(a), len(b)
if not 1 <= k <= n + m:
raise ValueError("k out of range")
left, right = max(0, k - m), min(k, n)
while left <= right:
i = left + (right - left) // 2
j = k - i
al = a[i - 1] if i else float("-inf")
ar = a[i] if i < n else float("inf")
bl = b[j - 1] if j else float("-inf")
br = b[j] if j < m else float("inf")
if al <= br and bl <= ar:
return max(al, bl)
if al > br:
right = i - 1
else:
left = i + 1
raise ValueError("Inputs must be sorted")#include <algorithm>
#include <climits>
#include <stdexcept>
#include <vector>
int kth_two_sorted(const std::vector<int>& a, const std::vector<int>& b, int k) {
if (a.size() > b.size()) return kth_two_sorted(b, a, k);
int n = static_cast<int>(a.size()), m = static_cast<int>(b.size());
if (k < 1 || k > n + m) throw std::invalid_argument("k out of range");
int left = std::max(0, k - m), right = std::min(k, n);
while (left <= right) {
int i = left + (right - left) / 2, j = k - i;
long long al = i ? a[i - 1] : LLONG_MIN;
long long ar = i < n ? a[i] : LLONG_MAX;
long long bl = j ? b[j - 1] : LLONG_MIN;
long long br = j < m ? b[j] : LLONG_MAX;
if (al <= br && bl <= ar) {
return static_cast<int>(std::max(al, bl));
}
if (al > br) right = i - 1;
else left = i + 1;
}
throw std::invalid_argument("Inputs must be sorted");
}