Kth Smallest Reading When Merging Two Sorted Sensor Logs
Implement kthSmallestReading
Given two sensor logs,
logA and logB, each already sorted in non-decreasing order (possibly empty, but never both at once), and an integer k, find the k-th smallest reading across both logs combined — without actually merging them into one list first.
The direct approach merges the two logs (an easy O(m+n) two-pointer walk, since both are already sorted) and then simply reads off the value at index k-1. That works, but it builds the entire merged log even though only one position in it is ever needed — wasteful once the logs get large. The faster approach reuses the same partition binary searchBinary Search on the PartitionInstead of searching over array values or over a range of candidate answers, this binary search hunts for a cut position (an index) in the shorter array. A cut is valid once every value kept on its left side is ≤ every value kept on its right side across both arrays combined — exactly the ordering a real merge would produce, found without ever performing the merge. idea used to find a combined median: search for the one cut position across both logs whose left side holds exactly the first k combined values, with every left value ≤ every right value. Once that cut is found, the k-th smallest reading is read directly off its boundary — in O(log(min(m, n))) time, without merging anything.
Example 1:
Input: logA = [11,23,38], logB = [7,19,30,52], k = 4
Output: 23
Example 2:
Input: logA = [5,12], logB = [1,2,3,4,5,6], k = 1
Output: 1
Example 3:
Input: logA = [5,12], logB = [1,2,3,4,5,6], k = 8
Output: 12
+ 10 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ length of logA ≤ 1000 - ●
0 ≤ length of logB ≤ 1000 - ●
logA and logB are never both empty - ●
1 ≤ k ≤ length of logA + length of logB - ●
-10⁶ ≤ logA[i], logB[i] ≤ 10⁶ - ●
Both logA and logB are sorted in non-decreasing order
logA =
[11, 23, 38]
logB =
[7, 19, 30, 52]
k =
4