Find the Difference of Two Arrays

Given two integer arrays nums1 and nums2, return a list of two lists: the distinct values of nums1 that are not in nums2, and the distinct values of nums2 that are not in nums1. Order does not matter. This is LeetCode 2215.

Example 1
Input: nums1 = [1, 2, 3], nums2 = [2, 4, 6]
Output: [[1, 3], [4, 6]]
Example 2
Input: nums1 = [1, 2, 3, 3], nums2 = [1, 1, 2, 2]
Output: [[3], []]
Explanation: 3 is reported once, even though it appears twice.

How to Think About It

Step 1: Remove repeats first

The answer lists each value once. Turning each array into a HashSet removes repeats and gives O(1) membership checks.

Step 2: Set difference, both ways

  • For each value in set1, keep it if set2 does not contain it.
  • Do the same the other way round.

With Java collections, set1.removeAll(set2) on a copy does the first part in one call; the loops make the idea explicit.

Walkthrough

Example 2: set1 = {1, 2, 3}, set2 = {1, 2}.

ValueIn set1?In set2?Goes to
1yesyesneither
2yesyesneither
3yesnofirst list

Result: [[3], []].

Java Solution

toSet builds a set from an array; the two loops collect the values unique to each side.

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

public class FindTheDifferenceOfTwoArrays {

    public static List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        Set<Integer> set1 = toSet(nums1);
        Set<Integer> set2 = toSet(nums2);
        List<Integer> only1 = new ArrayList<>();
        for (int x : set1) {
            if (!set2.contains(x)) {
                only1.add(x);
            }
        }
        List<Integer> only2 = new ArrayList<>();
        for (int x : set2) {
            if (!set1.contains(x)) {
                only2.add(x);
            }
        }
        return List.of(only1, only2);
    }

    private static Set<Integer> toSet(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            set.add(x);                       // also removes repeats
        }
        return set;
    }

    public static void main(String[] args) {
        System.out.println(findDifference(new int[] {1, 2, 3}, new int[] {2, 4, 6}));
        // [[1, 3], [4, 6]]
        System.out.println(findDifference(new int[] {1, 2, 3, 3}, new int[] {1, 1, 2, 2}));
        // [[3], []]
    }
}

The original implementation, FindDifferenceOfTwoArrays.java, is on GitHub.

Complexity

  • Time: O(m + n).
  • Space: O(m + n) for the sets.

Using a set to answer "have I seen this?" in O(1) is also the core of Contains Duplicate.