Find the Difference of Two Arrays — LeetCode #2215 (Easy)
Tags: Array, Hash Table
Related patterns: Hash Map, Array
Brute Force approach
Time complexity: O(n²). Space complexity: O(1).
The brute force approach checks each element of the first array against all elements of the second array. This is straightforward but inefficient as it requires nested loops.
The time complexity is O(n²) because for each element in nums1, we check against all elements in nums2, leading to a nested loop.
- Step 1: Initialize two empty lists, answer1 and answer2.
- Step 2: For each element in nums1, check if it exists in nums2. If not, add it to answer1.
- Step 3: For each element in nums2, check if it exists in nums1. If not, add it to answer2.
- Step 4: Return [answer1, answer2].
Input: nums1 = [1,2,3], nums2 = [2,4,6]
1. Initialize answer1 = [], answer2 = []
2. Check 1 in nums2: not found, add to answer1 -> answer1 = [1]
3. Check 2 in nums2: found, do nothing
4. Check 3 in nums2: not found, add to answer1 -> answer1 = [1, 3]
5. Check 2 in nums1: found, do nothing
6. Check 4 in nums1: not found, add to answer2 -> answer2 = [4]
Optimal Solution approach
Time complexity: O(n). Space complexity: O(n).
Using sets allows us to efficiently find distinct elements and check for membership in constant time, significantly improving performance.
The time complexity is O(n) because we traverse each array once to create sets and then perform set operations which are efficient.
- Step 1: Convert nums1 and nums2 into sets to eliminate duplicates.
- Step 2: Use set difference to find elements in nums1 not in nums2 and vice versa.
- Step 3: Return the results as lists.
Input: nums1 = [1,2,3], nums2 = [2,4,6]
1. Create set1 = {1, 2, 3}, set2 = {2, 4, 6}
2. Calculate answer1 = set1 - set2 = {1, 3}
3. Calculate answer2 = set2 - set1 = {4, 6}
4. Return [[1, 3], [4, 6]]
Key Insights
- Using sets can significantly reduce the time complexity for membership checks.
- Distinct elements can be easily managed with sets, avoiding duplicates automatically.
Common Mistakes
- Not considering duplicates in the input arrays, leading to incorrect results.
- Using nested loops without realizing the inefficiency, especially for larger inputs.
Interview Tips
- Always think about the data structures you can use to optimize your solution.
- Discuss your thought process and approach with the interviewer before coding.
- Test your solution with edge cases, such as empty arrays or arrays with all elements the same.
