K-th Element of Two Sorted Arrays

New·Hard·Binary Search

Partition so exactly k values sit on the left

Asked at:AmazonGoogleMicrosoftMeta

Practice mode

Step

Initialization

Cut A somewhere in 0…4 — bounds chosen so B's matching cut stays inside its own array — and let B's cut be k minus that.

Recursion workspace

Partition by Binary Search

Step 1 / 3init

100%

low

high

Explanation

The arrays were swapped so A is the shorter one. Same partition idea as the median, but the left side now holds exactly k elements instead of half. The k-th smallest is then the largest value on that side.

step 1 / 3

Space play← → stepHome reset

TimeO(log min(m, n))·SpaceO(1)

Partition by Binary Search

1function kthElement(a, b, k) {
2  const m = a.length, n = b.length;
3 
4  // Always binary search the shorter array
5  if (m > n) return kthElement(b, a, k);//m: 4n: 5k: 5low: 0high: 4
6 
7  const left = k;
8 
9  // Bounds keep b's matching cut inside b
10  let low = Math.max(0, k - n);
11  let high = Math.min(k, m);
12 
13  while (low <= high) {
14    const mid1 = (low + high) >> 1;
15    const mid2 = left - mid1;
16 
17    const l1 = (mid1 > 0) ? a[mid1 - 1] : Number.MIN_SAFE_INTEGER;
18    const l2 = (mid2 > 0) ? b[mid2 - 1] : Number.MIN_SAFE_INTEGER;
19    const r1 = (mid1 < m) ? a[mid1]     : Number.MAX_SAFE_INTEGER;
20    const r2 = (mid2 < n) ? b[mid2]     : Number.MAX_SAFE_INTEGER;
21 
22    // Left side holds the k smallest — answer is its largest
23    if (l1 <= r2 && l2 <= r1) {
24      return Math.max(l1, l2);
25    } else if (l1 > r2) {
26      high = mid1 - 1;
27    } else {
28      low = mid1 + 1;
29    }
30  }
31  return -1;
32}

low0

high4

Command Palette

K-th Element of Two Sorted Arrays

K-th Element of Two Sorted Arrays