Kth Element of Two Sorted Arrays

Kth Element of Two Sorted Arrays asks for the k-th smallest value if you merged two already-sorted arrays — without paying to merge them fully. It is a clean exercise in the two-pointer merge walk that powers merge sort, with a neat early stop.

The slow way first

The obvious idea: actually merge the two arrays into one sorted list, then return index k - 1. That works and is easy to reason about, but it builds the entire merged array of size n + m and keeps walking even after the answer is known. That is O(n + m) time and O(n + m) extra space — wasteful when k is small.

The question to ask: do I really need the whole merge? No. I only need the first k values in sorted order. So I can stop the walk the instant I have taken k of them.

The idea: merge, but stop at k

Keep two pointers, i into A and j into B, each sitting on the next unconsumed value. At every step, compare the two front values and take the smaller one — advance its pointer and tick a running count. The moment count equals k, the value you just took is the answer.

The key insight: because both arrays are already sorted, the smaller of the two current fronts is always the next value in global sorted order. So the k-th value we take is exactly the k-th smallest overall — no need to look at anything past it.

Walk through it

Step through the animation. Pointer i rides array A, pointer j rides array B, and count ticks up underneath. We take 1 (from A), then 2 (from B), then 3 (from A), then 4 (from B) — and the moment count reaches k = 4, the value just taken, 4, is the answer. We never look at 5 or 6.

Pseudocode

i = j = count = 0
while both arrays still have a value:
    if A[i] <= B[j]:
        taken = A[i];  i += 1
    else:
        taken = B[j];  j += 1
    count += 1
    if count == k:
        return taken            # the kth value taken
# one array ran out: the rest are the next-smallest in order
return (A[i:] + B[j:])[k - count - 1]

The Python solution

def kth(A, B, k):
    i = j = count = 0
    while i < len(A) and j < len(B):
        if A[i] <= B[j]:
            taken = A[i]
            i += 1
            count += 1
        else:
            taken = B[j]
            j += 1
            count += 1
        if count == k:
            return taken
    rest = A[i:] + B[j:]      # one array ran out
    return rest[k - count - 1]

• i, j are the two read positions; count tracks how many values we have taken so far.
• The while runs only while both arrays still have a value to compare.
• if A[i] <= B[j] — take from A when its front is smaller or equal; otherwise take from B. taken remembers the value we just consumed.
• Lines 12–13 are the early stop: as soon as count == k, the value just taken is the k-th smallest, so we return immediately.
• If one array empties before we reach k, the remaining values (A[i:] + B[j:]) are already in sorted order, so the answer is the (k - count - 1)-th of them.

Complexity

The merge walk does only k comparisons and uses O(1) extra space (just the pointers and a counter). When k is large there is a sharper trick: a binary-search variant that, on each step, discards k/2 elements from one array at a time, reaching the answer in O(log(n + m)) time. It is faster but much fiddlier to get right; the linear merge walk is the one to reach for first in an interview, then mention the log version as the optimization.

When this pattern shows up

Practice