Problem: Union of Two Sorted Arrays

Let’s look at a problem that is a small variation on the merge.

This is the union of the two arrays, in the set sense. A value that is in arr1, or in arr2, or in both, belongs in the result once.

Take arr1 = [1, 3, 5, 7] and arr2 = [2, 3, 6, 7, 9]:

arr1:  ┌───┬───┬───┬───┐
       │ 1 │ 3 │ 5 │ 7 │
       └───┴───┴───┴───┘

arr2:  ┌───┬───┬───┬───┬───┐
       │ 2 │ 3 │ 6 │ 7 │ 9 │
       └───┴───┴───┴───┴───┘

The union is [1, 2, 3, 5, 6, 7, 9]. The values 3 and 7 appear in both inputs and appear once in the result. Notice that the result has seven values, not nine. The two inputs have nine values between them, and two of those are shared.

The signature of the method in Java might look like this:

public static int[] union(int[] arr1, int[] arr2) {
  // Your implementation goes here
}

Let’s think of some special or edge cases as well:

• If either array is empty, the union is a copy of the other array.
• If both arrays are empty, the union is an empty array.
• If the two arrays share no values, the union is just the merge of the two, and its length is the sum of their lengths.
• If the two arrays are identical, the union is a copy of either one.

There is one constraint: the solution must run in $O(n+m)$ time, where $n$ and $m$ are the lengths of the two arrays. That rules out checking each value of one array against every value of the other.