Find the Difference of Two Arrays
EasyPrompt
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:
Input: 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:
Input: 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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. We iterate through each element of the first array and, for each element, we scan the entire second array to see if a match exists. We repeat the process for the second array against the first. To handle the requirement for distinct elements in the output, we use sets to store our results before converting them to lists.
Algorithm
- Initialize two empty sets,
resultSet1andresultSet2, to store the unique differences. - For each element
num1innums1:- Set a boolean flag
is_presenttofalse. - Iterate through each element
num2innums2. - If
num1equalsnum2, setis_presenttotrueand break the inner loop. - If the inner loop completes and
is_presentisfalse, addnum1toresultSet1.
- Set a boolean flag
- Repeat the process, swapping the roles of
nums1andnums2to populateresultSet2. - Convert
resultSet1andresultSet2to lists. - Return a list containing the two result lists.
Walkthrough
We need to find two lists: diff1 (elements in nums1 but not nums2) and diff2 (elements in nums2 but not nums1).
To find diff1, we iterate through each number num1 in nums1. For each num1, we perform a linear search through nums2. If after checking all elements of nums2, we don't find num1, we add it to a result set to ensure uniqueness.
Similarly, to find diff2, we iterate through each number num2 in nums2 and search for it in nums1. If not found, it's added to another result set.
Using sets (HashSet in Java) for the results is crucial to automatically handle duplicates from the input arrays (e.g., [1,2,3,3]) and ensure the final output lists contain only distinct integers.
Finally, the two sets are converted into lists and returned.
import java.util.*; class Solution { public List<List<Integer>> findDifference(int[] nums1, int[] nums2) { Set<Integer> diff1 = new HashSet<>(); Set<Integer> diff2 = new HashSet<>(); // Find elements in nums1 but not in nums2 for (int num1 : nums1) { boolean found = false; for (int num2 : nums2) { if (num1 == num2) { found = true; break; } } if (!found) { diff1.add(num1); } } // Find elements in nums2 but not in nums1 for (int num2 : nums2) { boolean found = false; for (int num1 : nums1) { if (num2 == num1) { found = true; break; } } if (!found) { diff2.add(num2); } } List<List<Integer>> answer = new ArrayList<>(); answer.add(new ArrayList<>(diff1)); answer.add(new ArrayList<>(diff2)); return answer; }}Complexity
Time
O(n * m), where `n` is the length of `nums1` and `m` is the length of `nums2`. For each of the `n` elements in `nums1`, we iterate through all `m` elements of `nums2`. The same happens for `nums2` against `nums1`.
Space
O(n + m) in the worst case, to store the result sets. If all elements in `nums1` are unique and not in `nums2`, and vice-versa, the sets will store `n` and `m` elements respectively.
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient for large arrays, likely resulting in a 'Time Limit Exceeded' error on most coding platforms.
A more optimized approach involves sorting both arrays first. Once sorted, we can use a two-pointer technique to compare elements from both arrays in a single pass. This avoids the nested loops of the brute-force method.
Algorithm
- Sort the input arrays
nums1andnums2. - Initialize two pointers,
i = 0andj = 0, fornums1andnums2respectively. - Initialize two sets,
diff1anddiff2, to store the results. - While
iis within the bounds ofnums1andjis within the bounds ofnums2:- If
nums1[i] < nums2[j], addnums1[i]todiff1and incrementi. - If
nums1[i] > nums2[j], addnums2[j]todiff2and incrementj. - If
nums1[i] == nums2[j], it's a common element. Store the value, then advanceipast all duplicates of this value innums1and advancejpast all duplicates innums2.
- If
- After the loop, if there are remaining elements in
nums1(i.e.,i < nums1.length), add them all todiff1. - Similarly, if there are remaining elements in
nums2, add them all todiff2. - Convert the sets to lists and return.
Walkthrough
The core idea is that if both arrays are sorted, we can find the differences efficiently. We initialize two pointers, i for nums1 and j for nums2, both starting at index 0.
We then compare nums1[i] and nums2[j]:
- If
nums1[i] < nums2[j], it meansnums1[i]is not present innums2. We addnums1[i]to our difference list fornums1and advance pointeri. - If
nums1[i] > nums2[j], it meansnums2[j]is not present innums1. We addnums2[j]to the difference list fornums2and advance pointerj. - If
nums1[i] == nums2[j], the element is common, so we advance both pointers.
A crucial part is handling duplicates. After processing an element, we must advance the pointer past all subsequent occurrences of that same element. We use sets to collect the results to naturally handle the distinctness requirement.
After the main loop finishes, one of the arrays might still have remaining elements. These are all guaranteed to be unique to that array, so we add them to the appropriate difference list.
import java.util.*; class Solution { public List<List<Integer>> findDifference(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); Set<Integer> diff1 = new HashSet<>(); Set<Integer> diff2 = new HashSet<>(); int i = 0, j = 0; int n = nums1.length; int m = nums2.length; while (i < n && j < m) { if (nums1[i] < nums2[j]) { diff1.add(nums1[i]); i++; } else if (nums1[i] > nums2[j]) { diff2.add(nums2[j]); j++; } else { // nums1[i] == nums2[j] int commonVal = nums1[i]; while (i < n && nums1[i] == commonVal) { i++; } while (j < m && nums2[j] == commonVal) { j++; } } } // Add remaining elements from nums1 while (i < n) { diff1.add(nums1[i]); i++; } // Add remaining elements from nums2 while (j < m) { diff2.add(nums2[j]); j++; } List<List<Integer>> answer = new ArrayList<>(); answer.add(new ArrayList<>(diff1)); answer.add(new ArrayList<>(diff2)); return answer; }}Complexity
Time
O(n log n + m log m), where `n` and `m` are the lengths of the arrays. The sorting steps take O(n log n) and O(m log m), and the subsequent two-pointer scan takes O(n + m). The sorting is the bottleneck.
Space
O(n + m) for the output lists. The space used by the sorting algorithm (e.g., `Arrays.sort` in Java uses O(log n) for primitives) is typically less than the space for the output.
Trade-offs
Pros
Much more efficient than brute force for large arrays.
Cons
The sorting step dominates the time complexity.
Can be slightly more complex to implement correctly, especially handling duplicates.
The most efficient approach utilizes hash sets to achieve linear time complexity. By converting both input arrays into sets, we can leverage the O(1) average time complexity of set lookups (the contains operation) to find the differences quickly.
Algorithm
- Create a hash set,
set1, and populate it with all elements fromnums1. - Create another hash set,
set2, and populate it with all elements fromnums2. - Initialize an empty list,
diff1. - Iterate through each
numinset1. Ifset2.contains(num)is false, addnumtodiff1. - Initialize an empty list,
diff2. - Iterate through each
numinset2. Ifset1.contains(num)is false, addnumtodiff2. - Return a list containing
diff1anddiff2.
Walkthrough
First, we convert nums1 and nums2 into two separate hash sets, set1 and set2. This step has two benefits: it gives us fast O(1) lookups, and it automatically handles any duplicate numbers within the original arrays.
Next, we find the elements that are unique to nums1. We iterate through every number in set1 and check if it exists in set2. If a number from set1 is not found in set2, we add it to our first result list.
Then, we do the reverse. We iterate through every number in set2 and check if it exists in set1. If a number from set2 is not found in set1, we add it to our second result list.
Finally, we return the two result lists. This method is clean, easy to read, and highly performant.
import java.util.*;import java.util.stream.Collectors; class Solution { public List<List<Integer>> findDifference(int[] nums1, int[] nums2) { // Step 1: Convert arrays to sets to get unique elements Set<Integer> set1 = new HashSet<>(); for (int num : nums1) { set1.add(num); } Set<Integer> set2 = new HashSet<>(); for (int num : nums2) { set2.add(num); } // Step 2: Find elements in set1 but not in set2 List<Integer> diff1 = new ArrayList<>(); for (int num : set1) { if (!set2.contains(num)) { diff1.add(num); } } // Step 3: Find elements in set2 but not in set1 List<Integer> diff2 = new ArrayList<>(); for (int num : set2) { if (!set1.contains(num)) { diff2.add(num); } } // Step 4: Return the result List<List<Integer>> answer = new ArrayList<>(); answer.add(diff1); answer.add(diff2); return answer; }}Complexity
Time
O(n + m) on average. It takes O(n) to build `set1`, O(m) to build `set2`, O(n) to iterate `set1` and check `set2`, and O(m) to iterate `set2` and check `set1`.
Space
O(n + m). We need space for `set1` (up to `n` elements) and `set2` (up to `m` elements), in addition to the space for the final answer lists.
Trade-offs
Pros
Optimal time complexity.
The code is often simpler and more declarative than the two-pointer approach.
Cons
Uses extra space to store the two sets, which might be a concern in memory-constrained environments.
Solutions
Solution
class Solution {public List<List<Integer>> findDifference(int[] nums1, int[] nums2) { Set<Integer> s1 = convert(nums1); Set<Integer> s2 = convert(nums2); List<List<Integer>> ans = new ArrayList<>(); List<Integer> l1 = new ArrayList<>(); List<Integer> l2 = new ArrayList<>(); for (int v : s1) { if (!s2.contains(v)) { l1.add(v); } } for (int v : s2) { if (!s1.contains(v)) { l2.add(v); } } ans.add(l1); ans.add(l2); return ans; }private Set<Integer> convert(int[] nums) { Set<Integer> s = new HashSet<>(); for (int v : nums) { s.add(v); } return s; }}/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[][]} */ var findDifference = function (nums1, nums2) { let ans1 = new Set(nums1), ans2 = new Set(nums2); for (let num of nums1) { ans2.delete(num); } for (let num of nums2) { ans1.delete(num); } return [Array.from(ans1), Array.from(ans2)]; };class Solution {public: vector<vector<int>> findDifference(vector<int> &nums1, vector<int> &nums2) { unordered_set<int> s1(nums1.begin(), nums1.end()); unordered_set<int> s2(nums2.begin(), nums2.end()); vector<vector<int>> ans(2); for (int v : s1) if (!s2.count(v)) ans[0].push_back(v); for (int v : s2) if (!s1.count(v)) ans[1].push_back(v); return ans; }};class Solution: def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]: s1, s2 = set(nums1), set(nums2) return [list(s1 - s2), list(s2 - s1)]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.