Kth Smallest Reading When Merging Two Sorted Sensor Logs
Solve this ProblemlogA 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.
Test Case 1:
Test Case 2:
Test Case 3:
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
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Merge Both Logs, Then Index Straight In
BruteSince both logA and logB are already individually sorted, merge them the classic merge-sort way: walk two pointers, always taking whichever front value is smaller, until one log runs out, then copy over whatever's left of the other. Once the full merged log exists, the k-th smallest reading is simply the value sitting at index k-1. Correct and only O(m+n), but it builds the entire merged log even though only one position in it is ever actually needed.
O(m + n)O(m + n)1class Solution {
2 public int kthSmallestReading(int[] logA, int[] logB, int k) {
3 int[] merged = new int[logA.length + logB.length];
4 int i = 0, j = 0, w = 0;
5 while (i < logA.length && j < logB.length) {
6 if (logA[i] <= logB[j]) merged[w++] = logA[i++];
7 else merged[w++] = logB[j++];
8 }
9 while (i < logA.length) merged[w++] = logA[i++];
10 while (j < logB.length) merged[w++] = logB[j++];
11 return merged[k - 1];
12 }
13}Optimal — Binary Search on the Partition
OptimalBinary search directly for the correct partition, the same idea used to find a combined median without merging: pick a cut position i in the shorter log and let j = k - i be forced so the left side always holds exactly the first k combined values. If the two logs' boundary values disagree — one side's rightmost "kept" value exceeds the other side's leftmost "discarded" value — shift the cut and try again. Once both boundaries agree, the largest value kept on the left is exactly the k-th smallest reading overall, found in O(log(min(m, n))) without ever merging anything.
O(log(min(m, n)))O(1)1class Solution {
2 private static final int NEG = -2000000000, POS = 2000000000;
3
4 public int kthSmallestReading(int[] logA, int[] logB, int k) {
5 int[] a = logA, b = logB;
6 if (a.length > b.length) { int[] t = a; a = b; b = t; }
7 int m = a.length, n = b.length;
8 int lo = Math.max(0, k - n), hi = Math.min(k, m);
9 while (lo <= hi) {
10 int i = lo + (hi - lo) / 2;
11 int j = k - i;
12 int aLeft = (i == 0) ? NEG : a[i - 1];
13 int aRight = (i == m) ? POS : a[i];
14 int bLeft = (j == 0) ? NEG : b[j - 1];
15 int bRight = (j == n) ? POS : b[j];
16 if (aLeft <= bRight && bLeft <= aRight) {
17 return Math.max(aLeft, bLeft);
18 } else if (aLeft > bRight) {
19 hi = i - 1;
20 } else {
21 lo = i + 1;
22 }
23 }
24 return -1;
25 }
26}