
Description
The problem involves finding the intersection of two arrays, where the intersection is defined as the common elements between two arrays without duplication. We are required to return an array of these unique common elements.
Intuition
If we can efficiently track the elements in both arrays and identify which ones are present in both, we can solve the problem. Using sets, which allow for fast lookups and only store unique elements, helps reduce complexity when determining the intersection.
Approach
- Convert both input arrays into sets. This removes duplicates and allows for quick lookup operations.
- Iterate over the elements in one set and check if they exist in the other set.
- If an element exists in both sets, add it to the result.
- Return the result as a list of integers.
Complexity
Time Complexity:
O(n + m), where n
is the size of the first array and m
is the size of the second array. This is because we need to traverse both arrays to populate the sets, and then iterate over one of the sets to find common elements.
Space Complexity:
O(n + m), for storing the two sets and the result list.
Code
C++
class Solution {
public:
std::vector intersection(std::vector& nums1, std::vector& nums2) {
std::set set1(nums1.begin(), nums1.end());
std::set set2(nums2.begin(), nums2.end());
std::vector result;
for (const auto& num : set2) {
if (set1.count(num)) {
result.push_back(num);
}
}
return result;
}
};
Python
class Solution:
def intersection(self, nums1, nums2):
set1 = set(nums1)
set2 = set(nums2)
result = []
for num in set2:
if num in set1:
result.append(num)
return result
Java
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set set1 = new HashSet<>();
Set set2 = new HashSet<>();
List result = new ArrayList<>();
for (int num : nums1) {
set1.add(num);
}
for (int num : nums2) {
if (set1.contains(num)) {
set2.add(num);
}
}
int[] resArray = new int[set2.size()];
int index = 0;
for (int num : set2) {
resArray[index++] = num;
}
return resArray;
}
}
JavaScript
var intersection = function (nums1, nums2) {
let set1 = new Set(nums1);
let set2 = new Set(nums2);
let result = []
for (let nums of set2) {
if (set1.has(nums)) {
result.push(nums)
}
}
return result
};