628. The kth Smallest Across Two Sorted Lists
Two lists are given, each already in non-decreasing order. Print the kth smallest value of
the two taken together, counting duplicates separately and counting from 1.
1 3 5 and 2 4 6, k = 4 -> 4 merged: 1 2 3 4 5 6
1 1 1 and 1 1, k = 5 -> 1
## Do not merge, then index
Building the merged list costs O(n + m) time AND O(n + m) memory, and most of it is thrown
away. Walking the merge without storing it needs no memory at all, and stops after k steps.
## Two pointers, k steps
i = 0, j = 0
repeat k times:
if i < n and (j == m or a[i] <= b[j]): last = a[i]; i += 1
else: last = b[j]; j += 1
answer: last
The condition reads awkwardly and each part is load-bearing:
· i < n guards reading past the end of the first list
· j == m takes from the first list when the second is exhausted
· a[i] <= b[j] is the ordinary comparison
Writing it as a[i] <= b[j] alone crashes as soon as either list runs out, which happens on
every input where k reaches past the shorter list.
## Duplicates count separately
1 1 1 and 1 1 with k = 5 answers 1, because the merged list has five entries. Equal
values are not collapsed; the question is about POSITIONS in the merge, not distinct values.
The <= rather than < in the comparison makes ties take from the first list, which changes
which pointer moves but never changes the ANSWER, since the values are equal.
## The faster method, and why it is not required here
There is an O(log(n + m)) method that discards k/2 elements at a time by comparing
midpoints. It is the right answer when k is huge and the lists are enormous, and it is
considerably harder to get right.
Here k is at most n + m, so the walk is already linear in the input, and linear is optimal
when the whole input may have to be read. Reaching for the logarithmic version here would be
complexity without benefit.
## Boundaries
k = 1 is the smaller of the two first values. k = n + m is the largest value overall. Either
list may be empty.
## Cost
Time O(k), which is at most O(n + m). Space O(1).
Constraints - `0 ≤ n, m ≤ 200000` and `n + m ≥ 1` - `1 ≤ k ≤ n + m` - `-10^9 ≤ each value ≤ 10^9` - both lists are non-decreasing
Input
The first line contains three integers n, m and k.
The second line contains n integers in non-decreasing order, and is absent when n is 0.
The third line contains m integers in non-decreasing order, and is absent when m is 0.
Output
Print one integer, the kth smallest value of the two lists combined.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.