Advertisement
Home Data Structure Arrays Find Difference of Two Arrays

Find Difference of Two Arrays

0
Advertisement

Title: Find Difference of Two Arrays

In this guide, you will learn how to find the difference between two arrays in Java, a classic interview warm-up that also shows up as LeetCode 2215. Given two integer arrays, nums1 and nums2, the goal is to return two lists: the values that appear only in nums1, and the values that appear only in nums2.

This problem is a great vehicle for practicing Set-based thinking. You will see how trading a nested loop for a HashSet turns a slow, repeated-scan solution into a fast one, and why removing duplicates correctly matters for getting a clean, distinct result.

Understanding the Problem

You are given two integer arrays, nums1 and nums2, that may contain duplicate values. You must return a list of two lists: the first containing every distinct value that exists in nums1 but not in nums2, and the second containing every distinct value that exists in nums2 but not in nums1. The order of the values inside each list does not matter.

For example, if nums1 = [1, 2, 3] and nums2 = [2, 4, 6], the result is [[1, 3], [4, 6]] since 1 and 3 only appear in nums1, while 4 and 6 only appear in nums2. The value 2 is excluded because it is present in both arrays.

Approach / Algorithm Steps

Follow these steps to turn the problem statement into working code.

  1. Create two empty HashSet<Integer> objects, set1 and set2.
  2. Add every element of nums1 into set1; the set removes duplicates automatically.
  3. Add every element of nums2 into set2 the same way.
  4. Create two empty List<Integer> objects, onlyInFirst and onlyInSecond, to hold the results.
  5. Loop over every value in set1; if set2 does not contain that value, add it to onlyInFirst.
  6. Loop over every value in set2; if set1 does not contain that value, add it to onlyInSecond.
  7. Wrap onlyInFirst and onlyInSecond together in a List<List<Integer>> and return it.

Java Program

Here is a complete, compilable Java program that implements the steps above.

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

public class FindDifferenceOfTwoArrays {

    public static List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();

        for (int num : nums1) {
            set1.add(num);
        }
        for (int num : nums2) {
            set2.add(num);
        }

        List<Integer> onlyInFirst = new ArrayList<>();
        List<Integer> onlyInSecond = new ArrayList<>();

        for (int num : set1) {
            if (!set2.contains(num)) {
                onlyInFirst.add(num);
            }
        }
        for (int num : set2) {
            if (!set1.contains(num)) {
                onlyInSecond.add(num);
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        result.add(onlyInFirst);
        result.add(onlyInSecond);
        return result;
    }

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

        List<List<Integer>> difference = findDifference(nums1, nums2);

        System.out.println("Only in nums1: " + difference.get(0));
        System.out.println("Only in nums2: " + difference.get(1));
    }
}

Explanation of the Program

Walking through the code line by line shows why each step is necessary.

  • set1 and set2 store the distinct values of nums1 and nums2; using a HashSet makes every contains check run in constant time on average.
  • The first loop drops every value from set1 that also exists in set2, leaving only the values unique to nums1 inside onlyInFirst.
  • The second loop mirrors the first, filling onlyInSecond with values unique to nums2.
  • Wrapping onlyInFirst and onlyInSecond in a single List<List<Integer>> lets the method return both results from one call.
  • The main method demonstrates the method with a small sample input and prints both resulting lists.

Step-by-Step Trace

Trace the first loop on nums1 = [4, 4, 1, 7] and nums2 = [7, 1, 9]. After deduplication, set1 = {4, 1, 7} and set2 = {7, 1, 9}; the goal is to see which values survive into onlyInFirst.

IterationValue from set1In set2?onlyInFirst (before)onlyInFirst (after)
14no[][4]
21yes[4][4]
37yes[4][4]

At the end of each iteration, onlyInFirst holds every value visited so far from set1 that set2 does not contain, so once the loop finishes it holds exactly the values unique to nums1.

Examples

These examples cover a plain case, a case with duplicates, and a case with no difference at all.

Example 1: Simple Non-Overlapping Values

Input: nums1 = [1, 2, 3], nums2 = [2, 3, 4].

Java
int[] nums1 = {1, 2, 3};
int[] nums2 = {2, 3, 4};
// findDifference(nums1, nums2) returns [[1], [4]]

Example 2: Arrays With Duplicate Elements

Input: nums1 = [1, 1, 2, 2], nums2 = [2, 2, 3, 3]. Duplicates inside each array are removed automatically because the values are stored in a HashSet before comparison.

Java
int[] nums1 = {1, 1, 2, 2};
int[] nums2 = {2, 2, 3, 3};
// findDifference(nums1, nums2) returns [[1], [3]]

Example 3: Identical Arrays

Input: nums1 = [5, 6, 7], nums2 = [7, 6, 5]. Every value in nums1 also appears in nums2, so both result lists come back empty.

Java
int[] nums1 = {5, 6, 7};
int[] nums2 = {7, 6, 5};
// findDifference(nums1, nums2) returns [[], []]

Common Mistakes to Avoid

These are the mistakes that most often turn this easy-sounding problem into a buggy submission.

  • Comparing arrays with nested loops – checking every element of nums1 against every element of nums2 with two nested for loops works on tiny inputs but slows down badly as the arrays grow. Build a HashSet first so each membership check is constant time.
  • Reusing one set for both arrays – adding both nums1 and nums2 into the same Set overwrites the first array’s values before the comparison runs, so onlyInFirst comes back empty. Keep set1 and set2 separate.
  • Iterating the raw array instead of the set – looping over nums1 directly rather than over set1 adds the same value to onlyInFirst once per duplicate occurrence. Loop over the deduplicated set instead.
  • Checking membership with Arrays.asList().contains() – calling Arrays.asList(nums2).contains(num) inside the loop rescans the whole array on every call, which brings back the slow nested-loop behavior even though a list was involved. Use set2.contains(num) instead.

Edge Cases to Test

Before calling the solution finished, walk through these boundary inputs.

  • Empty nums1 or nums2
  • Both arrays empty
  • Arrays containing duplicate elements
  • Identical arrays, producing no difference
  • Completely disjoint arrays
  • Single-element arrays
  • Negative numbers and zero mixed together
  • Integer.MIN_VALUE / Integer.MAX_VALUE present

Additional Considerations

Beyond correctness, it helps to understand the cost of this approach and what to reach for when its assumptions do not hold.

Time and Space Complexity

Let n be the length of nums1 and m be the length of nums2. Building set1 and set2 takes O(n + m) time, and scanning each set once more to fill onlyInFirst and onlyInSecond adds another O(n + m), so the whole algorithm runs in O(n + m) time.

Space usage is also O(n + m), since set1 and set2 each hold up to the number of distinct values in their source array, and the two result lists hold the final answer.

Sorting-Based Alternative

If allocating two hash sets is undesirable, sort both arrays first and walk them with two pointers, advancing whichever pointer points at the smaller value and recording values that only appear under one pointer. This runs in O(n log n + m log n) time but avoids hashing, trading time for a different kind of simplicity.

Interview Follow-up Questions

A real interview rarely stops at the base problem. Expect variations like these.

  • What if you need the values common to both arrays instead of the differences? – intersect set1 and set2 by keeping only the values present in both, instead of only the values present in one.
  • What if nums1 and nums2 arrive already sorted? – use a two-pointer walk across both arrays instead of hashing, which avoids the extra set allocations while still running in linear time.
  • What if the arrays are too large to fit in memory at once? – sort each array externally in chunks, then merge-compare the sorted chunks in a streaming fashion so only a small window of each array is held in memory at a time.
  • What if you must solve this without allocating any extra Set or List? – sort both arrays in place, then compare them with two pointers, writing matches and mismatches directly without auxiliary hash-based storage.
  • What if you are given k arrays instead of two, and need the values unique to each one? – build a frequency map from value to the set of array indices containing it, then report values whose index set has size one, grouped by which array they came from.

Conclusion

Finding the difference of two arrays comes down to one core idea: trade an array scan for a HashSet lookup so membership checks become constant time instead of linear. Once set1 and set2 exist, filtering each one against the other is straightforward.

Try adapting this solution to the follow-up questions above, especially the sorted-input and k-array variants; they are common ways interviewers probe whether you understand why the hash-based approach works, not just how to type it. You can learn more about array-based interview problems in the Arrays category.