Find the Difference of Two Arrays
Easy
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 innums1which are not present innums2.answer[1]is a list of all distinct integers innums2which are not present innums1.
Note that the integers in the lists may be returned in any order.
Example 1:
nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums1. Therefore, answer[1] = [4,6].
Example 2:
nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].
Constraints:
1 <= nums1.length, nums2.length <= 1000-1000 <= nums1[i], nums2[i] <= 1000
Solution
Naive Solution
The brute force approach involves iterating through each element of nums1 and checking if it exists in nums2. If an element from nums1 is not found in nums2, it's added to the first result list. The same process is then repeated, but in reverse, with elements from nums2 being checked against nums1 to construct the second result list.
Code (Python)
def find_disappeared_numbers_naive(nums1, nums2):
distinct_nums1 = []
distinct_nums2 = []
for num in nums1:
if num not in nums2 and num not in distinct_nums1:
distinct_nums1.append(num)
for num in nums2:
if num not in nums1 and num not in distinct_nums2:
distinct_nums2.append(num)
return [distinct_nums1, distinct_nums2]
Time Complexity
O(m*n), where 'm' is the length of nums1 and 'n' is the length of nums2. This is because, for each element in nums1, we potentially iterate through all of nums2 (and vice versa).
Space Complexity
O(m + n) in the worst case, where 'm' is the number of distinct elements in nums1 that are not in nums2, and 'n' is the number of distinct elements in nums2 that are not in nums1. This accounts for the space used to store the two result lists.
Optimal Solution
A more efficient approach utilizes sets. Sets provide near-constant time complexity for membership checks. We can convert nums1 and nums2 into sets and then find the difference between them.
Code (Python)
def find_disappeared_numbers_optimal(nums1, nums2):
set1 = set(nums1)
set2 = set(nums2)
distinct_nums1 = list(set1 - set2)
distinct_nums2 = list(set2 - set1)
return [distinct_nums1, distinct_nums2]
Time Complexity
O(m + n), where 'm' is the length of nums1 and 'n' is the length of nums2. This is because converting the lists to sets takes O(m) and O(n) time, respectively. The set difference operation takes O(m) and O(n) as well.
Space Complexity
O(m + n), where 'm' is the number of elements in nums1 and 'n' is the number of elements in nums2. This accounts for the space used to store the two sets.
Edge Cases
- Empty arrays: If either
nums1ornums2is empty, the corresponding result list will contain all the elements from the non-empty array. - Duplicate elements: The use of sets automatically handles duplicate elements, ensuring that each distinct number appears only once in the result.
- Arrays with the same elements: If
nums1andnums2contain the same elements, both result lists will be empty.
