Kth element of two sorted arrays

Medium

Problem

Given two sorted arrays, return the kth smallest element (1-indexed) of their combined sorted order, without merging them. Aim for O(log(min(m, n))).

Example 1

Input:  a = [2, 3, 6, 7, 9], b = [1, 4, 8, 10], k = 5
Output: 6

Also asked as: K-th Element of Two Sorted Arrays

Test cases

Case 1

Input:    [2,3,6,7,9], [1,4,8,10], 5
Expected: 6

Case 2

Input:    [100,112,256,349,770], [72,86,113,119,265,445,892], 7
Expected: 256

Case 3

Input:    [1], [2], 2
Expected: 2

Case 4

Input:    [], [3,4], 2
Expected: 4

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Merge until k (simple)

Time O(k)Space O(1)

Two pointers; take k−1 smaller heads, the kth is the answer.

function kthElement(a, b, k) {
let i = 0, j = 0;
while (true) {
if (i === a.length) return b[j + k - 1];
if (j === b.length) return a[i + k - 1];
if (k === 1) return Math.min(a[i], b[j]);
a[i] <= b[j] ? i++ : j++;
k--;
}
}

2. Binary search on the split (O(log)

Time O(log(min(n, m)))Space O(1)

Same partition idea as "median of two sorted arrays": pick how many come from a, derive the rest from b, adjust until the split is valid.

function kthElement(a, b, k) {
if (a.length > b.length) [a, b] = [b, a];
let lo = Math.max(0, k - b.length), hi = Math.min(k, a.length);
while (lo <= hi) {
const i = (lo + hi) >> 1, j = k - i;
const aL = i > 0 ? a[i - 1] : -Infinity;
const aR = i < a.length ? a[i] : Infinity;
const bL = j > 0 ? b[j - 1] : -Infinity;
const bR = j < b.length ? b[j] : Infinity;
if (aL <= bR && bL <= aR) return Math.max(aL, bL);
if (aL > bR) hi = i - 1; else lo = i + 1;
}
}