Find Common Elements Between Two Arrays
Problem
You are given two integer arrays nums1 and nums2. Return an array answer of length 2 where answer[0] is the count of indices i such that nums1[i] also exists in nums2, and answer[1] is the count of indices i such that nums2[i] also exists in nums1.
nums1 = [2,3,2], nums2 = [1,2][2,1]def find_intersection_values(nums1, nums2):
set1 = set(nums1)
set2 = set(nums2)
a = sum(1 for x in nums1 if x in set2)
b = sum(1 for x in nums2 if x in set1)
return [a, b]function findIntersectionValues(nums1, nums2) {
const set1 = new Set(nums1);
const set2 = new Set(nums2);
let a = 0, b = 0;
for (const x of nums1) if (set2.has(x)) a++;
for (const x of nums2) if (set1.has(x)) b++;
return [a, b];
}class Solution {
public int[] findIntersectionValues(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for (int x : nums1) set1.add(x);
for (int x : nums2) set2.add(x);
int a = 0, b = 0;
for (int x : nums1) if (set2.contains(x)) a++;
for (int x : nums2) if (set1.contains(x)) b++;
return new int[]{a, b};
}
}vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set1(nums1.begin(), nums1.end());
unordered_set<int> set2(nums2.begin(), nums2.end());
int a = 0, b = 0;
for (int x : nums1) if (set2.count(x)) a++;
for (int x : nums2) if (set1.count(x)) b++;
return {a, b};
}Explanation
The answer has two parts that mirror each other: count how many entries of nums1 are present somewhere in nums2, and symmetrically count how many entries of nums2 are present in nums1. Note these count indices, so duplicates are counted each time.
To test membership quickly we build a set from each array. Looking up whether a value exists in a set is constant time, which turns the whole problem into two simple scans.
For answer[0] we walk nums1 and increment whenever the current value is in set2. For answer[1] we walk nums2 and increment whenever the value is in set1. We iterate the original arrays, not the sets, so repeated values each add to the count.
Using sets only for the lookup side, while iterating the raw array for counting, is the key detail — it gives membership in O(1) without losing the duplicate occurrences that the problem wants counted.
Example: nums1 = [2,3,2], nums2 = [1,2]. In nums1, both 2's are in nums2 but 3 is not, so a = 2. In nums2, only 2 is in nums1, so b = 1. Answer [2,1].