Kth element of two sorted arrays
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
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; }}