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