Solution: Union

The union $A\cup B$ contains every element that is in $A$ or in $B$. Let $m$ be the size of $A$ and $n$ the size of $B$. In the code, arr1 holds $A$ and arr2 holds $B$.

On an unsorted set

LinkedSet and ArraySet store their elements in no particular order, so we build the union directly. Start with all of $A$, then iterate over $B$ and add the elements that are not already in $A$:

public static int[] union(int[] arr1, int[] arr2) {
  int[] result = new int[arr1.length + arr2.length];
  int k = 0;
  for (int i = 0; i < arr1.length; i++) {
    result[k++] = arr1[i];
  }
  for (int j = 0; j < arr2.length; j++) {
    if (!contains(arr1, arr2[j])) {
      result[k++] = arr2[j];
    }
  }
  return trim(result, k);
}

The method uses two helpers. The first, contains, is a linear search:

private static boolean contains(int[] arr, int value) {
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] == value) {
      return true;
    }
  }
  return false;
}

The second, trim, handles the length of the result. We do not know how many values the union has until the second loop is done, because that depends on how many values the two arrays share. So we allocate result at length $m+n$, which is the most values the union can have, and k counts the slots we fill. Then trim copies the first k values into an array of length k. The union of two sorted arrays in the merge sort practice ends the same way:

private static int[] trim(int[] arr, int length) {
  int[] trimmed = new int[length];
  for (int t = 0; t < length; t++) {
    trimmed[t] = arr[t];
  }
  return trimmed;
}

The first loop copies $A$’s $m$ elements, each of them distinct, so that is $m$ appends. The cost is in the second loop: for each of $B$’s $n$ elements we check whether it already appears in $A$, and that check is a linear scan of $A$, $O(m)$ each time. Over $n$ elements, that is $O(m\cdot n)$. The trim copies at most $m+n$ values, which does not change the total. So the union costs $O(m\cdot n)$.

This is the same for both unsorted implementations, since both find an element by scanning. The move-to-front and transpose heuristics do not change it: they improve the average position of an element that is searched for often, but a union searches for each element of $B$ once, so no element is searched for more often than the others and the worst case is still $O(m\cdot n)$.

On a sorted set

SortedArraySet keeps its array in sorted order, so we can use the merge from merge sort. Iterate over both arrays at once with a pointer into each, always copying the smaller element to the result and advancing its pointer. The one change is for equal elements: merge sort copies both, but a set holds no duplicates, so we copy that element once and advance both pointers. This is SortedUnion.union, the solution to the union of two sorted arrays from the merge sort practice:

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
    }
  }
  int[] trimmed = new int[k];
  for (int t = 0; t < k; t++) {
    trimmed[t] = result[t];
  }
  return trimmed;
}

Because both arrays are sorted, when arr1[i] < arr2[j] no later element of arr2 can equal arr1[i], so we copy it and move on without ever scanning arr2 for a match. Each comparison advances at least one pointer, so the two pointers together take at most $m+n$ steps, and every element of the union is copied exactly once. So the union is $O(m+n)$. The elements also come out in sorted order, so we build the result by appending to the end of its array. There is no shifting and no scan for duplicates, and the result is a valid SortedArraySet.

Cost comparison

Earlier, keeping the array sorted gave us an $O(\log n)$ contains. Here it gives us a linear-time union.