Find the Difference of Two Arrays
Given two integer arrays nums1nums2nums1nums2nums2nums1
Example 1
Output: [[1, 3], [4, 6]]
Example 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
Step 2: Set difference, both ways
- For each value in
, keep it ifset1 does not contain it.set2 - Do the same the other way round.
With Java collections, set1.removeAll(set2)
Walkthrough
Example 2: set1 = {1, 2, 3}set2 = {1, 2}
| Value | In set1? | In set2? | Goes to |
|---|---|---|---|
| 1 | yes | yes | neither |
| 2 | yes | yes | neither |
| 3 | yes | no | first list |
Result: [[3], []]
Java Solution
toSet
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,
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