K-th Smallest of Two Sorted Arrays
You get two arrays of integers, a and b. Each one is sorted in ascending order. You also get an integer k.
Imagine putting all values of both arrays into one sorted list. Return the value at position k in that list, counting from 1.
Note
- Values can repeat, inside one array and across the two. Each copy counts as its own position.
- One of the arrays can be empty, but not both.
Try to solve it in O(log(min(n, m))) time, without building the merged list.
Hint: suppose you take i values from the front of a and k - i values from the front of b. Those are the k smallest exactly when the last value taken from each side is not bigger than the first value left on the other side. Binary search for i.
Examples
Example 1
- Input:
- [3,8,15,21], [1,9,10], 5
- Output:
- 10
Together, in order: 1, 3, 8, 9, 10, 15, 21. The 5th value is 10.
Example 2
- Input:
- [], [-2,4,6], 1
- Output:
- -2
a is empty, so the answer comes from b alone. The 1st value is -2.
Example 3
- Input:
- [5,5,7], [5,6], 4
- Output:
- 6
Together, in order: 5, 5, 5, 6, 7. Each 5 takes its own position, so the 4th value is 6.
Constraints
0 <= a.length, b.length <= 251 <= a.length + b.length1 <= k <= a.length + b.length-1000 <= a[i], b[j] <= 1000aandbare each sorted in ascending order.
Run checks your code against the 3 examples. Submit checks it against all 243 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.