263. Union of Two Sorted Lists
Two lists, each already in non-decreasing order and each possibly containing duplicates. Print every value that appears in either list, each exactly once, in increasing order.
A set would do this and would cost memory proportional to the input and would throw away the ordering you were handed. Because both lists are sorted, two pointers produce the answer in one pass with no extra structure.
Three things happen at each step: take from the left, take from the right, or take one and skip the other when they are equal. Duplicates within a list are skipped by comparing with whatever was written last.
Constraints - `0 ≤ n ≤ 100000` - `0 ≤ m ≤ 100000` - `1 ≤ n + m` - `-1000000000 ≤ values ≤ 1000000000`
Input
The first line contains two integers n and m.
The second line contains n integers in non-decreasing order.
The third line contains m integers in non-decreasing order.
A line is empty when its count is zero.
Output
Print the union in increasing order, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.