Workspace

Problem workspace

3 day streakD

Kth Element of Two Sorted Arrays

HardBinary SearchTwo-array partitions

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.

A = shorter array · green = left partitionk = 5
A · cut = —104182103B · cut = —2031627394
Current comparisonLeft partitionNumbers below = indices
Left cut bound
0
Cut in A
—
Right cut bound
4
Step 01 / 3

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 − i

Recorded result so far

Not resolved
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")

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap