Kth Element of Two Sorted Arrays
MediumPartition so the left holds k
Cleverly skip past numbers in both sorted lists to land on the k-th smallest without merging them.
The idea
The same partition idea, but the combined left half must hold exactly k elements; the answer is the larger of the two left maxima.
a[2,3,6,7,9]
b[1,4,8,10]
Step 1 of 11. Brute force: merge both sorted arrays, then read off the 5-th value. a [2,3,6,7,9], b [1,4,8,10].
1/11
Brute force
timeO(m+n)spaceO(m+n)
Merge then pick.
1const merged = [];2while (i < a.length || j < b.length) merged.push(takeSmaller());3return merged[k - 1];Memory
- last
- —
- a
- [2,3,6,7,9]
- b
- [1,4,8,10]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- a = [2, 3, 6, 7, 9], b = [1, 4, 8, 10], k = 5
- Output:
- 6
- Explanation:
- Merged, the 5th smallest is 6.
Example 2
- Input:
- a = [1, 2], b = [3, 4], k = 3
- Output:
- 3
- Explanation:
- The 3rd element overall is 3.
Example 3
- Input:
- a = [5], b = [2, 7], k = 1
- Output:
- 2
- Explanation:
- Smallest overall is 2.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.