Find the Difference of Two Arrays
The key idea
Convert each array to a set so duplicates collapse and membership tests are O(1). The first answer list is the elements of set1 that are not in set2; the second is the elements of set2 not in set1. Build both with one pass over each set.
Problem
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.
Note that the integers in the lists may be returned in any order.
Constraints
- 1 <= nums1.length, nums2.length <= 1000
- -1000 <= nums1[i], nums2[i] <= 1000
Examples
Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Complexity
Time: O(n + m) Space: O(n + m)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY
- Majority Element IIMEDIUM