Solution: Merge, Skipping the Ties

Let’s start from the merge we wrote in the chapter:

public static int[] merge(int[] arr1, int[] arr2) {
  int[] merged = new int[arr1.length + arr2.length];
  int i = 0, j = 0;
  for (int k = 0; k < merged.length; k++) {
    if (i >= arr1.length) {
      merged[k] = arr2[j++];
    } else if (j >= arr2.length) {
      merged[k] = arr1[i++];
    } else if (arr1[i] <= arr2[j]) {
      merged[k] = arr1[i++];
    } else {
      merged[k] = arr2[j++];
    }
  }
  return merged;
}

Two things about this code do not fit the union.

The first is the tie. When the two fronts are equal, the merge copies the one from arr1 and leaves the one from arr2 for the next step, so both copies end up in the output. For a union, an equal pair should produce one copy. So on a tie we should copy one value and advance both pointers.

The second is the length. The merge knows its output length up front, $n+m$, and its loop runs over the output. The union does not know how many values it will produce, because that depends on how many values the two arrays share, and we do not know that until the loop has consumed both arrays. So the loop cannot run over the output. It has to run over the inputs instead: keep going while either array still has values.

Let’s make both changes. The loop condition changes, and the comparison gains a third case. The two exhausted-array checks at the top stay as they are, because once one array runs out, there is nothing left for the other array’s values to tie with:

public static int[] union(int[] arr1, int[] arr2) {
  int[] result = new int[arr1.length + arr2.length];
  int i = 0, j = 0, k = 0;
  while (i < arr1.length || j < arr2.length) {
    if (i >= arr1.length) {
      result[k++] = arr2[j++];
    } else if (j >= arr2.length) {
      result[k++] = arr1[i++];
    } else if (arr1[i] < arr2[j]) {
      result[k++] = arr1[i++];
    } else if (arr1[i] > arr2[j]) {
      result[k++] = arr2[j++];
    } else {
      result[k++] = arr1[i++];  // a tie: copy the value once
      j++;                      // and skip its twin in arr2
    }
  }
  // ...
}

Since the loop no longer runs over the output, k is no longer the loop variable. It is a counter we advance ourselves, once per value we copy.

That also handles the length. We still allocate result at length $n+m$, because that is the most values the union can have, and k counts how many slots we actually fill. When the loop ends, k is the true length. So we copy the filled part into an array of that length and return it:

public static int[] union(int[] arr1, int[] arr2) {
  int[] result = new int[arr1.length + arr2.length];
  int i = 0, j = 0, k = 0;
  while (i < arr1.length || j < arr2.length) {
    if (i >= arr1.length) {
      result[k++] = arr2[j++];
    } else if (j >= arr2.length) {
      result[k++] = arr1[i++];
    } else if (arr1[i] < arr2[j]) {
      result[k++] = arr1[i++];
    } else if (arr1[i] > arr2[j]) {
      result[k++] = arr2[j++];
    } else {
      result[k++] = arr1[i++];
      j++;
    }
  }
  int[] trimmed = new int[k];
  for (int t = 0; t < k; t++) {
    trimmed[t] = result[t];
  }
  return trimmed;
}

Let’s trace it on arr1 = [1, 3, 5, 7] and arr2 = [2, 3, 6, 7, 9]. Both pointers start at the front:

arr1:  ┌───┬───┬───┬───┐         arr2:  ┌───┬───┬───┬───┬───┐
       │ 1 │ 3 │ 5 │ 7 │                │ 2 │ 3 │ 6 │ 7 │ 9 │
       └───┴───┴───┴───┘                └───┴───┴───┴───┴───┘
         ↑                                ↑
         i                                j

result: []

1 < 2, so we copy 1 and advance i. Then 3 > 2, so we copy 2 and advance j:

arr1:  ┌───┬───┬───┬───┐         arr2:  ┌───┬───┬───┬───┬───┐
       │░1░│ 3 │ 5 │ 7 │                │░2░│ 3 │ 6 │ 7 │ 9 │
       └───┴───┴───┴───┘                └───┴───┴───┴───┴───┘
             ↑                                ↑
             i                                j

result: [1, 2]

The shaded cells have been consumed. Now both fronts are 3. This is the tie. We copy 3 once and advance both pointers:

arr1:  ┌───┬───┬───┬───┐         arr2:  ┌───┬───┬───┬───┬───┐
       │░1░│░3░│ 5 │ 7 │                │░2░│░3░│ 6 │ 7 │ 9 │
       └───┴───┴───┴───┘                └───┴───┴───┴───┴───┘
                 ↑                                ↑
                 i                                j

result: [1, 2, 3]

5 < 6, copy 5, advance i. 7 > 6, copy 6, advance j. Then both fronts are 7, another tie, so we copy 7 once and advance both:

arr1:  ┌───┬───┬───┬───┐         arr2:  ┌───┬───┬───┬───┬───┐
       │░1░│░3░│░5░│░7░│                │░2░│░3░│░6░│░7░│ 9 │
       └───┴───┴───┴───┘                └───┴───┴───┴───┴───┘
                         ↑                                ↑
                         i                                j

result: [1, 2, 3, 5, 6, 7]

i has reached the end of arr1, but arr2 still has a value, so the loop keeps going. The first check sees that arr1 is exhausted and copies the 9. Now both arrays are exhausted and the loop stops. k is 7, and the trimmed array is [1, 2, 3, 5, 6, 7, 9].

Does this handle the edge cases correctly?

• If arr1 is empty, the first check is true on every step, so every value of arr2 is copied in order. The result is a copy of arr2. The same holds when arr2 is empty.
• If both arrays are empty, the loop never runs, k stays 0, and we return an empty array.
• If the arrays share no values, the tie case never runs, every value is copied, and k ends at $n+m$. The trimmed array is the same length as result.
• If the arrays are identical, every step is a tie, and the result is a copy of either one.

What does this cost? Every step of the loop advances at least one pointer, and each pointer can advance at most the length of its array, so the loop runs at most $n+m$ times. Each step is constant work. The final copy is another pass over at most $n+m$ values. So the time is $O(n+m)$, the same as the merge.

The auxiliary space is the result array of length $n+m$ plus the trimmed array, which is at most that long again. That is $O(n+m)$, also the same as the merge.