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:

1. answer1: How many numbers from nums1 are also found in nums2.
2. 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, you are just checking which numbers appear in both lists and counting them.

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 there are two 2s in nums1 that 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.

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 it 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.

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};
    }
};

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};
    }
}

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]

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];
};

But wait! Can we optimize it?

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 hash set, 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 hash set. 

Unlike lists or arrays where you may need to search through the entire collection to find an element, hash sets allow 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 hash set. A hash set 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 hash set. 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 hash set, and for each element in nums2, we check if it exists in the set. If it does, we increment the answer2.

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};
    }
};

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};
    }
}

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]

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];
};

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.