Find Common Elements Between Two Arrays — Problem & Solution
Find Common Elements Between Two Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find Common Elements Between Two Arrays is an easy coding problem on arrays and hash table, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two integer arrays nums1 and nums2.
Return an array [answer1, answer2] where:
answer1is the number of indicesisuch thatnums1[i]occurs somewhere innums2;answer2is the number of indicesisuch thatnums2[i]occurs somewhere innums1.
Repeated values are counted once per index.
Example 1
Input: nums1 = [2,3,2], nums2 = [1,2]
Output: [2,1]
Explanation: Both 2s of `nums1` occur in `nums2`; in `nums2` only the 2 occurs in `nums1`.
Example 2
Input: nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]
Output: [3,4]
Example 3
Input: nums1 = [3,4,2,3], nums2 = [1,5]
Output: [0,0]
Constraints
1 <= nums1.length, nums2.length <= 1001 <= nums1[i], nums2[i] <= 100
Hints for Find Common Elements Between Two Arrays
Hint 1
For each element you only need a yes/no answer: does its value appear in the other array?
Hint 2
Build a membership table (a set, or a boolean array since values are at most 100) for each array.
Hint 3
Then count the indices of each array whose value is marked in the other array's table.
How to solve Find Common Elements Between Two Arrays
Membership is all that matters, so precompute which values each array contains and count the indices whose value the other array contains.
Approach
- Mark
in1[v] = truefor everyvinnums1, andin2[v] = truefor everyvinnums2. answer1= number ofiwithin2[nums1[i]];answer2= number ofiwithin1[nums2[i]].- Return
[answer1, answer2].
Why it works
Each index is checked once against the exact set of values of the other array, so it is counted precisely when its value occurs there; duplicates are separate indices and are counted separately, as required.
Complexity
- Time —
O(n + m) - Space —
O(V) with V = 100
Pitfalls
- Counting distinct common values instead of indices undercounts repeated values.
- The two answers are not symmetric — compute each against the other array.
Reference solution
Python
from typing import List
def findIntersectionValues(nums1: List[int], nums2: List[int]) -> List[int]:
s1, s2 = set(nums1), set(nums2)
return [sum(1 for x in nums1 if x in s2), sum(1 for x in nums2 if x in s1)]Java
public static int[] findIntersectionValues(int[] nums1, int[] nums2) {
boolean[] in1 = new boolean[101], in2 = new boolean[101];
for (int v : nums1) in1[v] = true;
for (int v : nums2) in2[v] = true;
int a = 0, b = 0;
for (int v : nums1) if (in2[v]) a++;
for (int v : nums2) if (in1[v]) b++;
return new int[]{a, b};
}C++
vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {
bool in1[101] = {false}, in2[101] = {false};
for (int v : nums1) in1[v] = true;
for (int v : nums2) in2[v] = true;
int a = 0, b = 0;
for (int v : nums1) if (in2[v]) a++;
for (int v : nums2) if (in1[v]) b++;
return {a, b};
}JavaScript
var findIntersectionValues = function(nums1, nums2) {
var in1 = new Uint8Array(101), in2 = new Uint8Array(101);
for (var i = 0; i < nums1.length; i++) in1[nums1[i]] = 1;
for (var j = 0; j < nums2.length; j++) in2[nums2[j]] = 1;
var a = 0, b = 0;
for (var p = 0; p < nums1.length; p++) if (in2[nums1[p]]) a++;
for (var q = 0; q < nums2.length; q++) if (in1[nums2[q]]) b++;
return [a, b];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets