669. The Smallest Value Both Lists Hold

Two non-decreasing lists are given. Print the smallest value that appears in BOTH, or -1 when they share nothing.

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

## Walk both and stop at the first match

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

## Why the FIRST match is the smallest

Both lists are non-decreasing and both cursors only move forward, so the values under examination only ever increase. The first agreement is therefore the smallest value they can agree on, and the loop can stop immediately.

That early stop is the whole difference between this and problem 637, which collects every shared value. Same sweep, different stopping rule.

## Why advancing the smaller one is safe

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

## What a hash set would cost

Putting one list in a set and scanning the other is O(n + m) time and O(n) memory, and it does NOT give the smallest match without extra work: it finds matches in the order of the second list, which may not be the order of value if that list were unsorted.

Here both lists are sorted, so the sweep gets the ordering for free and uses no memory at all.

## Boundaries

Either list empty shares nothing. Lists that share only their last values still answer correctly, because the loop runs to the end.

Duplicates change nothing: the first match is found at the first copy.

## Cost

Time O(n + m). Space O(1).

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