637. The Values Both Lists Share

Two non-decreasing lists are given. Print the values they share, counting MULTIPLICITY: a value appearing p times in the first list and q times in the second appears min(p, q) times in the answer.

Print how many values are shared, then those values in non-decreasing order.

1 1 2 2 and 2 2 -> 2 2 2 4 5 9 and 4 4 9 9 -> 2 4 9 1 2 3 and 4 5 6 -> 0

## Not the same as problem 264

Problem 264 prints the intersection as a SET, so each shared value appears once. This keeps multiplicity, so 1 1 2 2 against 2 2 answers 2 2 rather than 2.

The two differ by exactly one line of code and produce different answers on any input with duplicates, which is why the statement spells the rule out and why the tests include duplicates on both sides.

## The sweep

i = 0, j = 0 while i < n and j < m: a[i] < b[j] -> i += 1 a[i] > b[j] -> j += 1 equal -> emit a[i]; i += 1; j += 1

Advancing BOTH on a match is what produces the multiplicity: a value present twice on each side is matched twice, once per pair of positions.

For the set version you would instead skip past every copy on both sides, which is the one line that differs.

## Why advancing the smaller one is safe

If a[i] < b[j], then a[i] is smaller than every value remaining in b, since b is non-decreasing from j onwards. So a[i] can match nothing that is left, and discarding it loses nothing.

## The output is already sorted

Both lists are non-decreasing and the sweep emits in increasing order of the matched value, so no final sort is needed.

## Boundaries

Either list empty gives 0 shared values and nothing after the count. No overlap gives the same.

## Cost

Time O(n + m). Space O(1) beyond the output.

Constraints - `0 ≤ n, m ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - both lists are non-decreasing