Problem
Given two integer arrays nums1 and nums2, return a list of two lists.The first list should contain all distinct integers that are present in nums1 but not in nums2. The second list should contain all distinct integers that are present in nums2 but not in nums1.
The order of the elements in the result does not matter.
Example(s)
Consider the following examples to understand the expected input and output.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],[]]Solution
This solution uses HashSet to store the distinct elements of both arrays. A set automatically removes duplicate values, allowing us to focus only on the elements that are present in one array but not the other.We create two sets and then check each element of nums1 against the set of nums2. If an element does not exist in
set2, it belongs to the first result list. Similarly, we check the elements of nums2 against set1 to build the second result list.
class Solution {
public 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> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
for (int num : set1) {
if (!set2.contains(num)) {
list1.add(num);
}
}
for (int num : set2) {
if (!set1.contains(num)) {
list2.add(num);
}
}
return Arrays.asList(list1, list2);
}
}Complexity
Building the two sets and checking their elements takesO(n + m) average time, where n and m are the lengths of nums1 and nums2.
The two sets store the distinct elements from both arrays, so the extra space complexity is
O(n + m).
