Find Common Elements Between Two Arrays
Problem Description:
You are given two lists of numbers. The first list is called nums1 and the second list is called nums2. Your task is to find:
- answer1: How many numbers from nums1 are also found in nums2.
- answer2: How many numbers from nums2 are also found in nums1.
After counting, you will return the two answers in a list like this: [answer1, answer2].
In simple terms, your is just to Find Common Elements Between Two Arrays
Example to Find Common Elements Between Two Arrays
Example 1:
Input: nums1 = [2,3,2], nums2 = [1,2]
Output: [2,1]
Explanation:
1. Looking at nums1:
- We check if any element in nums1 exists in nums2.
- The elements of nums1 are: 2, 3, and 2 (again).
- First element 2 exists in nums2 ([1, 2]), so we count it.
- Second element 3 does not exist in nums2, so we skip it.
- Third element 2 (repeated) also exists in nums2. We count it again because we're counting how many indices in nums1 match with nums2.
- Therefore, answer1 = 2 (as two 2s in nums1 exist in nums2).
2. Looking at nums2:
- We check if any element in nums2 exists in nums1.
- The elements of nums2 are 1 and 2.
- First element 1 does not exist in nums1 ([2, 3, 2]), so we skip it.
- Second element 2 exists in nums1, so we count it.
- Therefore, answer2 = 1 (as there is one 2 in nums2 that exists in nums1).
There are 2 elements from nums1 that exist in nums2 (2 and 2) and 1 element from nums2 that exists in nums1 (2).
Therefore, the output is [2, 1].
Example 2:
Input: nums1 = [3,4,2,3], nums2 = [1,5]
Output: [0,0]
Explanation:
1. Looking at nums1:
- We check if any element in nums1 exists in nums2.
- The elements of nums1 are 3, 4, 2, and 3 (again).
- None of these numbers (3, 4, 2) are present in nums2 ([1, 5]).
- Therefore, answer1 = 0 because there are no common elements between nums1 and nums2.
2. Looking at nums2:
- We check if any element in nums2 exists in nums1.
- The elements of nums2 are 1 and 5.
- None of these numbers (1 or 5) are present in nums1 ([3, 4, 2, 3]).
- Therefore, answer2 = 0 because none of the elements from nums2 exist in nums1.
No numbers are common between nums1 and nums2, so the answer is [0,0].
Constraints:
n == nums1.length
m == nums2.length
1 <= n, m <= 100
1 <= nums1[i], nums2[i] <= 100
Brute-force Approach:
When faced with this problem, the first approach that comes to mind is to manually compare the elements from one array with the elements of the other array.
This is the most intuitive way to solve the problem because it directly checks if each element of one list exists in the other by brute force comparison.
How does it work?
Okay, let’s suppose we are given two arrays, nums1, and nums2, and need to count how many elements from one array exist in the other.
For example, if an element x is in both nums1 and nums2, it should contribute to the count. This is a very basic operation—just checking if an element exists in the other list.
Our first idea is to check every element in nums1 and see if it's present in nums2. This is quite straightforward: pick an element from nums1, then scan through every element of nums2 to see if it exists.
Similarly, we can reverse this process for the second part of the problem. For every element in nums2, we check if it's in nums1.
How does it come to mind?
This idea is based on what we first think of when we encounter such a problem. If you're not considering advanced methods, you'd likely think: "I need to check each number one by one to see if it exists in the other array."
It’s a brute force approach because we are manually checking each element against every other element.
Let's walk through an Example:
Let’s walk through an example to understand the problem of common elements in two arrays with nums1 = [1, 2, 3] and nums2 = [2, 3, 4].
- answer1 (how many elements from nums1 exist in nums2):
- Check 1 in nums2 → No match.
- Check 2 in nums2 → Match (present in index 0)! Increase count by 1.
- Check 3 in nums2 → Match (present in index 1)! Increase count by 1.
- So, answer1 = 2.
- answer2 (how many elements from nums2 exist in nums1):
- Check 2 in nums1 → Match (present in index 1)! Increase count by 1.
- Check 3 in nums1 → Match (present in index 2)! Increase count by 1.
- Check 4 in nums1 → No match.
- So, answer2 = 2.
Okay, now we understand the approach, but how will we write it in code?
First, with a for loop, we will go through each element in nums1. For each element, we will again use a for loop to check all the elements in nums2 to see if they exist there.
If we find a match, we increase the count for answer1, which keeps track of how many elements from nums1 are also in nums2. We repeat this for every element in nums1.
Similarly, for answer2, we take each element from nums2 and check if it exists in nums1 by looping through all of its elements.
If a match is found, we increase the count for answer2, which tells us how many elements from nums2 are present in nums1. This process continues until we've checked all elements in both arrays.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {
int answer1 = 0;
int answer2 = 0;
// Calculate answer1: elements in nums1 that exist in nums2
for (int i = 0; i < nums1.size(); i++) {
for (int j = 0; j < nums2.size(); j++) {
if (nums1[i] == nums2[j]) {
answer1++;
// Stop searching after finding a match
break;
}
}
}
// Calculate answer2: elements in nums2 that exist in nums1
for (int i = 0; i < nums2.size(); i++) {
for (int j = 0; j < nums1.size(); j++) {
if (nums2[i] == nums1[j]) {
answer2++;
// Stop searching after finding a match
break;
}
}
}
return {answer1, answer2};
}
};2. Java Try on Compiler
class Solution {
public int[] findIntersectionValues(int[] nums1, int[] nums2) {
int answer1 = 0;
int answer2 = 0;
// Calculate answer1: elements in nums1 that exist in nums2
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
if (nums1[i] == nums2[j]) {
answer1++;
// Stop searching after finding a match
break;
}
}
}
// Calculate answer2: elements in nums2 that exist in nums1
for (int i = 0; i < nums2.length; i++) {
for (int j = 0; j < nums1.length; j++) {
if (nums2[i] == nums1[j]) {
answer2++;
// Stop searching after finding a match
break;
}
}
}
// Return result as an array
return new int[]{answer1, answer2};
}
}3. Python Try on Compiler
class Solution:
def findIntersectionValues(self, nums1, nums2):
answer1 = 0
answer2 = 0
# Calculate answer1: elements in nums1 that exist in nums2
for i in range(len(nums1)):
for j in range(len(nums2)):
if nums1[i] == nums2[j]:
answer1 += 1
# Stop searching after finding a match
break
# Calculate answer2: elements in nums2 that exist in nums1
for i in range(len(nums2)):
for j in range(len(nums1)):
if nums2[i] == nums1[j]:
answer2 += 1
# Stop searching after finding a match
break
return [answer1, answer2]4. Javascript Try on Compiler
var findIntersectionValues = function(nums1, nums2) {
let answer1 = 0;
let answer2 = 0;
// Calculate answer1: elements in nums1 that exist in nums2
for (let i = 0; i < nums1.length; i++) {
for (let j = 0; j < nums2.length; j++) {
if (nums1[i] === nums2[j]) {
answer1++;
// Stop searching after finding a match
break;
}
}
}
// Calculate answer2: elements in nums2 that exist in nums1
for (let i = 0; i < nums2.length; i++) {
for (let j = 0; j < nums1.length; j++) {
if (nums2[i] === nums1[j]) {
answer2++;
break;
}
}
}
return [answer1, answer2];
};Time Complexity: O(n*m)
For each element in the array, we traverse the entire array to count its occurrences. In the first loop, we go from index 0 to n, and for each iteration of this loop, we again traverse from index 0 to m in the second loop. This can be expressed as m + m + m + m….. repeated n times, so the time complexity is O(n) * O(m), resulting in a total time complexity of O(n * m).
Space Complexity: O(1)
Auxiliary Space: O(1)
Explanation: The auxiliary space refers to any extra space used by the algorithm, excluding the input. Here, apart from the input arrays, we only use a few variables (answer1, answer2, and the result array), so the auxiliary space is O(1).
Total Space Complexity: O(n + m)
However, we also store the input arrays nums1 and nums2, which require O(n) and O(m) space, respectively, where n is the size of nums1 and m is the size of nums2. Thus, the total space complexity, considering both the input arrays and the auxiliary space, is O(n + m). This accounts for the space used by the input arrays nums1 and nums2.
Will the Brute Force Approach Work Within the Given Constraints?
Let’s analyze the problem with respect to the given constraints:
Time Complexity Analysis:
The brute force approach involves using two nested loops to compare elements of nums1 with nums2 and vice versa.
For each element in nums1, we loop through every element in nums2 to check if the element exists. This is an O(n * m) operation. Similarly, we do the reverse for nums2 and nums1.
In total, we perform approximately O(n * m) operations, where:
- n is the size of nums1.
- m is the size of nums2.
Since the maximum value of n and m is 100 (as per the constraints), the worst-case scenario will result in 100 * 100 = 10,000 operations.
Time Complexity:
- Worst-case time complexity: O(n * m) = O(100 * 100) = O(10,000)
Given that modern systems can handle 10⁶ operations within acceptable time limits (e.g., under 1 second), this time complexity is efficient enough within the given constraints.
Conclusion:
The brute force approach with a time complexity of O(n * m) and space complexity of O(1) will work efficiently for the given constraints where
1 <= n, m <= 100. Even in the worst-case scenario, the number of operations is small enough to ensure that the code runs within a reasonable time limit. But what if the constraints of n,m<= 10000, then in the worst case, it can go
up to 1e8, which is unacceptable
Optimize Way To Find Common Elements Between Two Arrays
Now that we understand the brute force approach and its limitations, we can think of ways to optimize it. One key observation is that for each element, we are traversing the entire second array just to check if that element is present.
What if we could mark all elements in the second array, indicating whether they are present or not? This would eliminate the need for the second loop to traverse the array entirely.
We need a data structure that allows us to add or retrieve data in constant time, so we can instantly determine whether an element is present without having to go through the entire list. This significantly improves the efficiency of the process.
Can you think of a technique that allows us to access elements in constant time?
Yes, exactly! Hashing is one of the easiest and most effective ways to speed up this process, especially when we need to perform multiple lookups.
By using a hashset, we can store and retrieve data quickly, enabling much more efficient searches. Instead of scanning through the entire list each time to check for an element, we store the elements in a hashset.
What is a hashset?
A hashset is a data structure that stores unique elements and allows for fast lookups, insertions, and deletions. It works by using a hashing function to map each element to a specific "bucket" or location in memory, allowing for nearly constant time O(1) operations.
Unlike lists or arrays, where you may need to search through the entire collection to find an element, HashSet allows you to quickly check whether an element is present without scanning through everything. This makes them especially useful in scenarios where you need to check for the existence of elements frequently and efficiently.
How does it work?
Ok, Instead of looping through the entire second array for each element in the first array, we can store the elements of one array in a HashSet. A hashset allows us to check if an element exists in it in constant time, which is much faster than looping through the entire array.
We first store all the elements of nums2 in a hashset. Then, for each element in nums1, we just check if it exists in the set. If it does, we increment the answer1.
Similarly, we store all the elements of nums1 in another hashset, and for each element in nums2, we check if it exists in the set. If it does, we increment the answer2.
Let's walk through an example:
Let’s take an example to make this clearer.
Example:
- nums1 = [1, 2, 3, 4]
- nums2 = [3, 4, 5, 6]
Step 1: Store nums2 in a hashset:
set2 = {3, 4, 5, 6}
Step 2: For each element in nums1, check if it exists in set2:
- 1: not in set2
- 2: not in set2
- 3: in set2, so increment answer1
- 4: in set2, so increment answer1
answer1 = 2 (because 3 and 4 from nums1 exist in nums2).
Step 3: Similarly, store nums1 in a hashset:
set1 = {1, 2, 3, 4}
Step 4: For each element in nums2, check if it exists in set1:
- 3: in set1, so increment answer2
- 4: in set1, so increment answer2
- 5: not in set1
- 6: not in set1
answer2 = 2 (because 3 and 4 from nums2 exist in nums1).
Thus, the final answer is [2, 2].
How can we implement this in code?
To implement this approach in code, we will first create two hashset: one for each array (nums1 and nums2).
Then we will use a for loop to go through all the elements of nums1 and nums2 and add them to their respective hashset. This ensures that we have a quick way to check if an element exists in the other array.
Now, For every element in nums1, we check if it exists in the set that contains elements of nums2. If it does, we increment the answer1. Similarly, for every element in nums2, we check if it exists in the set that contains elements of nums1. If it does, we increment the answer2.
By doing this, we are able to determine:
How many elements in nums1 are present in nums2 (stored in answer1).
How many elements in nums2 are present in nums1 (stored in answer2).
The results are returned in the form of an array, where the first value represents answer1, which is the count of how many elements of nums1 exist in nums2. The second value represents answer2, which is the count of how many elements of nums2 exist in nums1.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
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 answer1 = 0, answer2 = 0;
// Calculate answer1: elements in nums1 that exist in nums2
for (int num : nums1) {
if (set2.count(num)) {
// If num exists in nums2
answer1++;
}
}
// Calculate answer2: elements in nums2 that exist in nums1
for (int num : nums2) {
if (set1.count(num)) {
// If num exists in nums1
answer2++;
}
}
return {answer1, answer2};
}
};2. Java Try on Compiler
class Solution {
public int[] findIntersectionValues(int[] nums1, int[] nums2) {
// Create sets to store the elements of nums1 and nums2
HashSet<Integer> set1 = new HashSet<>();
HashSet<Integer> set2 = new HashSet<>();
// Add elements of nums1 to set1
for (int num : nums1) {
set1.add(num);
}
// Add elements of nums2 to set2
for (int num : nums2) {
set2.add(num);
}
int answer1 = 0;
int answer2 = 0;
// Calculate answer1: elements in nums1 that exist in nums2
for (int num : nums1) {
if (set2.contains(num)) {
answer1++;
}
}
// Calculate answer2: elements in nums2 that exist in nums1
for (int num : nums2) {
if (set1.contains(num)) {
answer2++;
}
}
return new int[]{answer1, answer2};
}
}3. Python Try on Compiler
class Solution:
def findIntersectionValues(self, nums1, nums2):
set1 = set(nums1)
set2 = set(nums2)
answer1 = sum(1 for num in nums1 if num in set2)
answer2 = sum(1 for num in nums2 if num in set1)
return [answer1, answer2]4. Javascript Try on Compiler
var findIntersectionValues = function (nums1, nums2) {
let set1 = new Set(nums1);
let set2 = new Set(nums2);
let answer1 = 0, answer2 = 0;
// Calculate answer1
for (let num of nums1) {
if (set2.has(num)) {
answer1++;
}
}
// Calculate answer2
for (let num of nums2) {
if (set1.has(num)) {
answer2++;
}
}
return [answer1, answer2];
};Time Complexity: O(n + m)
As we are creating the hashsets, it takes O(n) time for nums1 and O(m) time for nums2. Checking each element in one array against the hashset of the other array takes O(n) for nums1 and O(m) for nums2. Since both loops are independent of each other, the overall time complexity is
O(n + m), which is much faster than the O(n * m) of the brute force approach.
Space Complexity: O(n + m)
As we are storing each element of nums1 and nums2 in separate hashset of size n and m, which are equal to the sizes of the arrays, the space complexity is O(n + m).
Auxiliary Space: O(n + m)
Explanation: The auxiliary space used for storing the hashset is also
O(n + m), as it requires space proportional to the number of unique elements in both arrays.
Total Space Complexity: O(n + m)
Therefore, the overall space complexity, considering both the hashset and the input arrays, is O(n + m).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an array of integer nums and an integer k, return the total number of continuous subarrays whose sum equals k.
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.