Shared Items of Two Sorted Lists
a and b are both sorted in non-decreasing order and may contain repeats. Return the items that appear in both lists, as a list in non-decreasing order. A value that appears x times in a and y times in b appears min(x, y) times in the answer.
Walk the two lists together with one index each: when the two current items are equal, record one and advance both; otherwise advance the list whose current item is smaller. Either list may be empty, and the answer is empty when nothing is shared.
Example 1
2 appears twice in both, 3 appears once in a and twice in b, so once; 1, 5 and 6 are not shared.
Example 2
The two lists have no value in common.
Constraints
0 <= len(a), len(b) <= 100-1000 <= a[i], b[i] <= 1000aandbare sorted in non-decreasing order
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.