# Kth Smallest in Two Sorted Arrays

# Kth Smallest in Two Sorted Arrays

Kth Smallest in Two Sorted Arrays selects an element from the sorted union of two arrays without explicitly merging them.

The main idea is to discard prefixes that cannot contain the answer. Since both arrays are sorted, comparing middle candidates lets us remove many elements at once.

## Problem

Given two sorted arrays $A$ and $B$, and a zero-based rank $k$, return the k-th smallest value in the combined sorted order.

The rank must satisfy:

$$
0 \le k < |A| + |B|
$$

## Algorithm

Use recursive elimination. Convert the zero-based rank to a one-based count:

$$
r = k + 1
$$

At each step, compare the $\lfloor r/2 \rfloor$-th remaining candidate from each array. The smaller candidate and all elements before it can be discarded.

```id="ktsa1"
kth_smallest_two_sorted(A, B, k):
    i = 0
    j = 0
    r = k + 1

    while true:
        if i == length(A):
            return B[j + r - 1]

        if j == length(B):
            return A[i + r - 1]

        if r == 1:
            return min(A[i], B[j])

        step = r // 2

        ai = min(i + step, length(A)) - 1
        bj = min(j + step, length(B)) - 1

        if A[ai] <= B[bj]:
            removed = ai - i + 1
            i = ai + 1
            r = r - removed
        else:
            removed = bj - j + 1
            j = bj + 1
            r = r - removed
```

## Example

Let:

$$
A = [1, 4, 8]
$$

and:

$$
B = [2, 3, 7, 9]
$$

The combined sorted order is:

$$
[1, 2, 3, 4, 7, 8, 9]
$$

For $k = 4$, the answer is:

$$
7
$$

## Correctness

At each step, the algorithm compares candidates near the middle of the remaining target rank. Suppose $A[ai] \le B[bj]$. Then every element from $A[i]$ through $A[ai]$ is less than or equal to $A[ai]$, and therefore less than or equal to $B[bj]$.

There are enough elements before or at these positions to prove that the discarded prefix of $A$ cannot contain the r-th remaining smallest element. The algorithm subtracts exactly the number of discarded elements from $r$, preserving the same target within the reduced arrays.

The symmetric argument applies when $B[bj] < A[ai]$. The loop ends when one array is exhausted or when $r = 1$, both of which are direct base cases.

## Complexity

| measure |        cost |
| ------- | ----------: |
| time    | $O(\log k)$ |
| space   |      $O(1)$ |

The method does not merge the arrays.

## When to Use

Use this algorithm when:

* both inputs are already sorted
* only one rank is needed
* merging would waste work
* arrays may be large

It is also the core subroutine for finding the median of two sorted arrays.

## Implementation

```id="ktsa2"
def kth_smallest_two_sorted(a, b, k):
    i = 0
    j = 0
    r = k + 1

    while True:
        if i == len(a):
            return b[j + r - 1]

        if j == len(b):
            return a[i + r - 1]

        if r == 1:
            return min(a[i], b[j])

        step = r // 2

        ai = min(i + step, len(a)) - 1
        bj = min(j + step, len(b)) - 1

        if a[ai] <= b[bj]:
            removed = ai - i + 1
            i = ai + 1
            r -= removed
        else:
            removed = bj - j + 1
            j = bj + 1
            r -= removed
```

```id="ktsa3"
func KthSmallestTwoSorted(a, b []int, k int) int {
	i, j := 0, 0
	r := k + 1

	for {
		if i == len(a) {
			return b[j+r-1]
		}

		if j == len(b) {
			return a[i+r-1]
		}

		if r == 1 {
			if a[i] < b[j] {
				return a[i]
			}
			return b[j]
		}

		step := r / 2

		ai := i + step - 1
		if ai >= len(a) {
			ai = len(a) - 1
		}

		bj := j + step - 1
		if bj >= len(b) {
			bj = len(b) - 1
		}

		if a[ai] <= b[bj] {
			removed := ai - i + 1
			i = ai + 1
			r -= removed
		} else {
			removed := bj - j + 1
			j = bj + 1
			r -= removed
		}
	}
}
```