Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:
-
answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
-
answer[1] is a list of all distinct integers in nums2 which are not present in nums1.
Please note that the integers in the lists may be returned in any order.
Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation: [1,3] numbers from nums1 are not present in nums2 array, and [4, 6] from nums2 are not present in nums1 array
Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation: 3 from nums1 is not present in nums2 array, and all numbers from nums2 are present in nums1 array.
Constraints:
- 1 <= nums1.length, nums2.length <= 1000
- -1000 <= nums1[i], nums2[i] <= 1000
Contents
- Solution 1 - Store input arrays into HashSet and find the difference
In this approach, we will first store input arrays nums1 and nums2 into HashSets nums1Set and nums2Set respectively,
then find differences between these two sets by iterating over elements of one set and check if they exist in the otehr set.
Then, we will loop through nums1Set and check if the number exists in nums2Set, if it does not exist then add it to result1
(List for difference between nums1 and nums2)
Implementation steps:
-
Create two HashSets, nums1Set, nums2Set and copy elements from nums1 into nums1Set and nums2 into nums2Set.
-
Next, create ArrayLists to collect the results into, result1 and result2.
-
Next, go through elements of nums1Set, and if the element doesn't exist in nums2Set, then add it to result1
and repeat the same step for nums2Set by checking element existence in nums1Set, and add it to result2
-
Finally, add list1 and list2 into another list and return that.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class FindDifferenceOfTwoArrays {
static List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
Set<Integer> nums1Set = new HashSet<>(nums1.length);
for(int num: nums1) {
nums1Set.add(num);
}
Set<Integer> nums2Set = new HashSet<>(nums2.length);
for(int num: nums2) {
nums2Set.add(num);
}
List<Integer> result1 = new ArrayList<>();
List<Integer> result2 = new ArrayList<>();
for(Integer num1 : nums1Set) {
if(!nums2Set.contains(num1)) {
result1.add(num1);
}
}
for(Integer num2 : nums2Set) {
if(!nums1Set.contains(num2)) {
result2.add(num2);
}
}
return List.of(result1, result2);
}
public static void main(String[] args) {
System.out.println(findDifference(new int[]{1, 2, 3}, new int[] {2, 4, 6}));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(m + n) time where m is the length of nums1
array and n is the length of nums2 (or) O(Max(m, n)).
Space complexity: O(m+n), since we are storing elements into HashSets.
Above implementations source code can be found at
GitHub link for Java code