Solution: Difference

The difference $A-B$ keeps the elements that are in $A$ but not in $B$. Unlike union and intersection, it is asymmetric: $A-B$ and $B-A$ are different sets. As before, $m$ is the size of $A$ and $n$ is the size of $B$, and arr1 holds $A$ and arr2 holds $B$.

On an unsorted set

Iterate over $A$ and keep each element that is not in $B$:

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

This is the intersection with the test negated, and it has the same cost, $O(m\cdot n)$. Because the difference is asymmetric, we must iterate over $A$. We cannot pick the smaller set to iterate over, the way we could for the intersection.

On a sorted set

We use the merge again, with the keep-rule changed to “in $A$, not in $B$”:

public static int[] sortedDifference(int[] arr1, int[] arr2) {
  int[] result = new int[arr1.length];
  int i = 0, j = 0, k = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result[k++] = arr1[i++];  // in arr1, not in arr2: copy
    } else if (arr1[i] > arr2[j]) {
      j++;                      // in arr2 only: skip
    } else {
      i++;                      // a tie: in both, exclude
      j++;
    }
  }
  while (i < arr1.length) {
    result[k++] = arr1[i++];    // what is left of arr1 is not in arr2
  }
  return trim(result, k);
}

The asymmetry changes the final step of the merge. When the first loop ends, we copy what is left of $A$, because those elements are greater than every element of $B$ and so cannot be in it. If $B$ still has elements left, the second loop does not run and we discard them. The merge is $O(m+n)$, and the result is sorted.

All three operations follow the same pattern. On an unsorted set they cost $O(m\cdot n)$, because each element of one set is searched for in the other. On a sorted set a single merge computes the result in $O(m+n)$, and the only thing that changes between union, intersection, and difference is the keep-rule.