Advertisement
Home Data Structure Arrays Find Symmetric Difference of Two Arrays

Find Symmetric Difference of Two Arrays

1
Advertisement

Title: Find Symmetric Difference of Two Arrays

In this guide, you will learn how to find the symmetric difference of two arrays in Java. The symmetric difference contains every element that appears in exactly one of the two arrays, so it excludes anything that shows up in both.

We will build this using HashSet for fast membership checks, walk through a full working program, trace it on a sample input, and then cover the edge cases and follow-up questions an interviewer is likely to ask.

Understanding the Problem

Given two integer arrays, arr1 and arr2, the symmetric difference is the set of values that belong to exactly one of the arrays. An element present in both arrays is excluded from the result, and duplicate values inside a single array only count once.

For example, if arr1 = [1, 2, 3] and arr2 = [2, 3, 4], the values 2 and 3 appear in both arrays and are dropped, leaving 1 from arr1 and 4 from arr2.

Approach / Algorithm Steps

  1. Convert arr1 into a HashSet<Integer> called set1 so membership checks run in constant time.
  2. Convert arr2 into a second HashSet<Integer> called set2.
  3. Create an empty list onlyInArr1 and iterate over set1, adding any value that is not found in set2.
  4. Create an empty list onlyInArr2 and iterate over set2, adding any value that is not found in set1.
  5. Package both lists together as the result, since the symmetric difference is really the union of these two exclusive lists.
  6. Return or print the two lists.

Java Program

Java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SymmetricDifference {

    public static List<List<Integer>> findSymmetricDifference(int[] arr1, int[] arr2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();

        for (int value : arr1) {
            set1.add(value);
        }
        for (int value : arr2) {
            set2.add(value);
        }

        List<Integer> onlyInArr1 = new ArrayList<>();
        List<Integer> onlyInArr2 = new ArrayList<>();

        for (int value : set1) {
            if (!set2.contains(value)) {
                onlyInArr1.add(value);
            }
        }
        for (int value : set2) {
            if (!set1.contains(value)) {
                onlyInArr2.add(value);
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        result.add(onlyInArr1);
        result.add(onlyInArr2);
        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {3, 4, 5, 6, 7};

        List<List<Integer>> symmetricDifference = findSymmetricDifference(arr1, arr2);

        System.out.println("Only in arr1: " + symmetricDifference.get(0));
        System.out.println("Only in arr2: " + symmetricDifference.get(1));
    }
}

Explanation of the Program

The method findSymmetricDifference starts by loading both arrays into HashSet instances, set1 and set2. Using a set instead of the original array removes duplicate values automatically and gives O(1) average-case lookups with contains().

The first loop walks set1 and keeps only the values that set2 does not contain; these go into onlyInArr1. The second loop does the mirror operation for set2, producing onlyInArr2.

Both lists are wrapped into a single List<List<Integer>> so the caller gets the full symmetric difference split by its source array, which mirrors how the result is typically expected in interview settings.

Step-by-Step Trace

Trace the algorithm on arr1 = [10, 20, 30, 40] and arr2 = [30, 40, 50, 60], where the target output is onlyInArr1 = [10, 20] and onlyInArr2 = [50, 60].

StepSourceValuePresent in Other Set?Action
1set110NoAdd to onlyInArr1
2set120NoAdd to onlyInArr1
3set130YesSkip
4set140YesSkip
5set230YesSkip
6set240YesSkip
7set250NoAdd to onlyInArr2
8set260NoAdd to onlyInArr2

At the end of each loop, the resulting list holds exactly the values from its source set that never appeared in the other set.

Examples

Example 1: Arrays With No Common Elements

When the two arrays share nothing in common, the symmetric difference is simply both arrays combined, split by source.

Java
int[] arr1 = {1, 3, 5};
int[] arr2 = {2, 4, 6};

List<List<Integer>> result = findSymmetricDifference(arr1, arr2);
System.out.println(result.get(0)); // [1, 3, 5]
System.out.println(result.get(1)); // [2, 4, 6]

Example 2: Arrays With Internal Duplicates

Duplicate values inside a single array collapse to one entry once the array is converted into a HashSet, so the output only reflects distinct values.

Java
int[] arr1 = {1, 1, 2, 2, 3};
int[] arr2 = {2, 3, 4, 4, 5};

List<List<Integer>> result = findSymmetricDifference(arr1, arr2);
System.out.println(result.get(0)); // [1]
System.out.println(result.get(1)); // [4, 5]

Example 3: Identical Arrays

When both arrays contain exactly the same values, every element is shared, so the symmetric difference is empty on both sides.

Java
int[] arr1 = {7, 8, 9};
int[] arr2 = {7, 8, 9};

List<List<Integer>> result = findSymmetricDifference(arr1, arr2);
System.out.println(result.get(0)); // []
System.out.println(result.get(1)); // []

Common Mistakes to Avoid

These are the mistakes that show up most often when candidates implement this problem under interview pressure.

  • Inverting the membership check – writing set2.contains(value) without the leading ! returns the intersection instead of the symmetric difference. Always negate the check so you keep values the other set does not contain.
  • Checking membership against a List – calling contains() on the raw array wrapped as a List makes every lookup O(n), turning the whole algorithm quadratic. Convert both arrays to HashSet first.
  • Expecting duplicates to survive – passing arr1 = {2, 2, 3} and expecting 2 to appear twice in the output. A HashSet dedupes by design, so the result only ever contains distinct values.
  • Skipping a null check – calling findSymmetricDifference(null, arr2) throws a NullPointerException on the first for loop. Validate both arrays before iterating if null input is possible.

Edge Cases to Test

Walk through these input shapes before calling the problem solved.

  • Empty arr1 or empty arr2
  • Both arrays empty
  • Identical arrays
  • Completely disjoint arrays
  • Arrays containing duplicate values
  • Single-element arrays
  • Integer.MIN_VALUE or Integer.MAX_VALUE present
  • Null array reference

Additional Considerations

The HashSet based approach runs in O(n + m) time, where n and m are the lengths of arr1 and arr2, since every insertion and lookup is O(1) on average.

Space usage is also O(n + m) because both arrays are copied into sets before any comparison happens. If the arrays arrive pre-sorted, a two-pointer merge-style scan can find the same result in O(n + m) time without building any sets, at the cost of needing sorted input.

Integer.MIN_VALUE and Integer.MAX_VALUE do not cause overflow here since the algorithm never arithmetically combines values, it only compares and stores them, so these extremes are safe once autoboxed into a HashSet<Integer>.

Interview Follow-up Questions

Once the base solution is working, expect the interviewer to push further with these variations.

  • What if both arrays are already sorted? – use a two-pointer merge-style scan instead of sets; advance whichever pointer points to the smaller value and record it only when the values differ.
  • What if you need the frequency of each exclusive element, not just its presence? – replace the HashSet with a HashMap<Integer, Integer> that counts occurrences per array, then compare counts instead of membership.
  • What if the arrays are too large to fit in memory at once? – sort each array externally in chunks and merge them in a single streaming pass, comparing chunk by chunk instead of loading everything into a set.
  • What if you must compute the result without any extra space beyond the output? – this is only possible when the inputs are sorted; the two-pointer merge approach needs no auxiliary set, only index variables.

Conclusion

Finding the symmetric difference of two arrays comes down to tracking which values exist in exactly one input, and a pair of HashSet instances makes that check a constant-time operation. Once you are comfortable with this pattern, try adapting it to count-based or sorted-input variants to see how the trade-offs between time, space, and ordering shift.

You can learn more about array-based problems like this one in the Arrays category on DailyJavaConcept.