aloalgoKth Element of Two Sorted Collections
Hard
You are given two sorted collections of numbers, coll1 and coll2, and an integer k, find the k-th smallest element in the conceptual combined sorted collection.
Note that k is 1-based, meaning k=1 refers to the smallest element. You should not merge the two collections to solve this problem.
Example 1
Inputs
coll1 = [1, 3, 5]
coll2 = [2, 4, 6]
k = 4
Output
4
Explanation:
The combined sorted collection would be [1, 2, 3, 4, 5, 6]. The 4th element is 4.
Example 2
Inputs
coll1 = [10, 20]
coll2 = [100, 200, 300]
k = 3
Output
100
Explanation:
The combined sorted collection would be [10, 20, 100, 200, 300]. The 3rd element is 100.
Example 3
Inputs
coll1 = [5]
coll2 = [1, 2, 3, 4]
k = 5
Output
5
Explanation:
The combined sorted collection would be [1, 2, 3, 4, 5]. The 5th element is 5.
Inputs
coll1 = [1, 3, 5]
coll2 = [2, 4, 6]
k = 4
Output
4