Find the uncommon elements from two sets

Question

I am trying to find the uncommon elements from two sets in Java. Here is my way:

private void findUnCommon{

    Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3, 4));
    Set<Integer> b = new HashSet<>(Arrays.asList(3, 4, 5, 6));
    // get all elements from set a and set b

    System.out.println("Before..");
    System.out.println("a is : " + a);
    System.out.println("b is : " + b);

    Set<Integer> result = new HashSet<>(a);
    result.removeAll(b);
    System.out.println("result is : " + result);

    Set<Integer> temp = new HashSet<>(b);
    temp.removeAll(a);
    System.out.println("temp is : " + temp);

    result.addAll(temp);
    System.out.println("Uncommon elements of set a and set b is : "
        + result);

    System.out.println("After..");
    System.out.println("a is : " + a);
    System.out.println("b is : " + b);
}

I have declared two extra sets. Can this be improved?

Answer 1

Is this a method? You can't just plop code anywhere in Java.

The name of the operation is symmetric difference, so you should probably call it that.

Here's a more compact implementation.

private Set<T> symmetricDifference(Set<T> a, Set<T> b) {
    Set<T> result = new HashSet<T>(a);
    for (T element : b) {
        // .add() returns false if element already exists
        if (!result.add(element)) {
            result.remove(element);
        }
    }
    return result;
}

Answer 2

With Apache Commons Collections (javadoc):

CollectionUtils.disjunction(a, b);

With Guava (javadoc):

Sets.symmetricDifference(a, b);

See also: Effective Java, 2nd edition, Item 47: Know and use the libraries (The author mentions only the JDK's built-in libraries but I think the reasoning could be true for other libraries too.)

Answer 3

This should work faster:

private void findUnCommon{

    Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3, 4));
    Set<Integer> b = new HashSet<>(Arrays.asList(3, 4, 5, 6));

    Set<Integer> result = new HashSet<>();
    for (Integer el: a) {
      if (!b.contains(el)) {
        result.add(el);
      }
    }
    for (Integer el: b) {
      if (!a.contains(el)) {
        result.add(el);
      }
    }
    System.out.println("Uncommon elements of set a and set b is : "
        + result);
}

Answer 4

If data is ordered, as is the case in your example, you can use a merge-sort algorithm to do it while traversing each collection only once:

    List<Integer> a = Arrays.asList(1, 2, 3, 4);
    List<Integer> b = Arrays.asList(3, 4, 5, 6);
    List<Integer> result = new ArrayList<>();

    int ia = 0, ib = 0;

    while(ia<a.size() && ib<b.size()) {
        if (a.get(ia)<b.get(ib)) {
            result.add(a.get(ia));
            ia++;
        } else if (a.get(ia)>b.get(ib)) {
            result.add(b.get(ib));
            ib++;
        } else {
            ia++;
            ib++;
        }
    }
    result.addAll(a.subList(ia, a.size()));
    result.addAll(b.subList(ib, b.size()));

    System.out.println("Uncommon elements of set a and set b is : " + result);

If an actual java.util.Set is required, instead of any collection that in this case behaves as a set, one may use a java.util.SortedSet implementation (e.g., java.util.TreeSet). The code above can be directly translated to iterators by using a PeekableIterator wrapper. Without peek(), it requires a little more effort to advance each iterator only when needed.