Dare2Solve
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.
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.
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.
O(n + m), for storing the two sets and the result list.
class Solution {
public:
std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
std::set<int> set1(nums1.begin(), nums1.end());
std::set<int> set2(nums2.begin(), nums2.end());
std::vector<int> result;
for (const auto& num : set2) {
if (set1.count(num)) {
result.push_back(num);
}
}
return result;
}
};
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
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
List<Integer> 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;
}
}
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
};