2956. Find Common Elements Between Two Arrays

EasyArrayHash Table
Leetcode Link

Problem Description

In this problem, we are provided with two arrays nums1 and nums2, each containing a set of integers. These arrays are 0-indexed, meaning that their indices start from 0. The main objective is to determine two specific values:

  1. The first value is the number of elements in nums1 that are also present in nums2. This doesn't mean exact index matching; as long as a value from nums1 shows up anywhere in nums2, it counts.

  2. The second value is similar but in the opposite direction: we count the number of elements in nums2 that are also present in nums1.

Our goal is to return these two counts as an array containing two integers, with the first value derived from nums1 and the second from nums2.

Intuition

For this problem, the intuitive approach is to effectively and efficiently determine whether elements of one array occur within the other. We can simplify the task by converting the arrays into sets, which allow us to check for the presence of an element in constant time (ignoring the initial cost of creating the set). This is due to the fact that sets in Python are implemented as hash tables, providing an average-case time complexity of O(1) for querying the presence of an item.

We follow these steps:

  1. Convert nums1 and nums2 into sets s1 and s2. This not only provides us with quick lookups but also removes duplicates, which are irrelevant to our counts since we're only interested in whether an element from one array is present at least once in the other.

  2. For the first count, we iterate through each element in nums1 (not s1, as we want the original array's indices) and check if it exists in s2. We sum these checks to get the total.

  3. For the second count, we perform a similar iteration, but now we loop over nums2 and check for the presence of each element in s1. We again sum the checks to get the total.

  4. These two sums give us the required values, and we return them as an array of size 2.

This approach gives us a solution that is efficient and takes full advantage of Python's set structure to minimize the time spent on lookups.

Solution Approach

The implementation of the solution uses the hash table data structure in Python, which is represented by the set. Sets are particularly useful in this scenario because they automatically handle duplicates and allow for efficient membership tests, which is exactly what we need.

Here is a walkthrough of the algorithm:

  1. Convert Lists to Sets:

    • We begin by converting the input lists nums1 and nums2 into sets, named s1 and s2. Converting to sets eliminates duplicates and enables us to perform quick lookups.
    • This is done using the syntax s1, s2 = set(nums1), set(nums2).
  2. Count Elements in Intersection: Since we are tasked with counting the elements of nums1 that are present in nums2 and vice versa, we proceed as follows:

    • For the first value, we iterate over each element in the original list nums1 using list comprehension and check if the element is in s2 (the set version of nums2). We use the expression sum(x in s2 for x in nums1) to count the number of True outcomes (which happen when x is in s2), effectively giving us the count of intersection elements pertaining to nums1.
    • Similarly, for the second value, we iterate over nums2 and check each element's presence in s1. Using the expression sum(x in s1 for x in nums2), we get the count of intersection elements pertaining to nums2.
  3. Return the Result:

    • After calculating both counts, we combine them into a list [sum(x in s2 for x in nums1), sum(x in s1 for x in nums2)] and return this list as our final result.

In terms of complexity:

  • Creating the sets from the lists has a time complexity of O(n) for nums1 and O(m) for nums2, where n and m are the lengths of the respective lists.
  • The list comprehensions that count the presences will also have a time complexity of O(n) and O(m) for nums1 and nums2 respectively.
  • Thus, the overall time complexity of this solution is O(n + m), which is quite efficient given that the lookups in the sets are O(1) operations on average.

By using sets for membership checks and list comprehensions for the counts, we achieve a concise and efficient implementation that aligns closely with the problem's requirements.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have two arrays:

  • nums1 = [1, 2, 2, 3]
  • nums2 = [2, 3, 4, 2]

We want to find the number of elements in nums1 that are present in nums2 and vice versa.

First, we convert nums1 and nums2 to sets to remove duplicates and allow efficient lookups. After conversion:

  • s1 = {1, 2, 3}
  • s2 = {2, 3, 4}

Next, we count the elements in nums1 that are also in s2:

  • Element 1 in nums1 is not in s2, count = 0
  • Element 2 in nums1 is in s2, count = 1
  • Element 2 in nums1 is in s2, count = 2 (repeated element, but we still count it)
  • Element 3 in nums1 is in s2, count = 3

So, there are 3 elements in nums1 that are present in nums2. We note that even though '2' is a duplicate in nums1, it is counted twice as it appears twice in the original array.

We repeat the process for nums2 against s1:

  • Element 2 in nums2 is in s1, count = 1
  • Element 3 in nums2 is in s1, count = 2
  • Element 4 in nums2 is not in s1, count = 2
  • Element 2 in nums2 is in s1, count = 3 (again, we count the duplicate)

We find there are 3 elements in nums2 that are present in nums1.

Lastly, we return the result as an array: [3, 3], representing the counts as required.

Through this example, we see how the solution approach handles array elements and their presence in the other array by using set operations and iteration to count the number of occurrences efficiently.

Solution Implementation

1class Solution:
2    def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
3        # Convert both lists to sets to remove duplicates and to allow for O(1) lookups
4        set_nums1, set_nums2 = set(nums1), set(nums2)
5      
6        # Calculate the sum of elements in nums1 that are also in set_nums2
7        # This counts the number of elements in nums1 present in the intersection
8        intersection_count1 = sum(x in set_nums2 for x in nums1)
9      
10        # Calculate the sum of elements in nums2 that are also in set_nums1
11        # This counts the number of elements in nums2 present in the intersection
12        intersection_count2 = sum(x in set_nums1 for x in nums2)
13      
14        # The function returns a list with both counts as elements
15        return [intersection_count1, intersection_count2]
16
17# Note: You need to import List from typing to use it as a type hint
18from typing import List
19
1// This class represents a solution for finding the intersection values between two arrays.
2class Solution {
3
4    // This method finds the intersection values between two integer arrays.
5    public int[] findIntersectionValues(int[] nums1, int[] nums2) {
6        // Arrays to store the presence of elements with a maximum value of 100 (since the array indices go from 0 to 100)
7        int[] presenceNums1 = new int[101];
8        int[] presenceNums2 = new int[101];
9      
10        // Mark the presence of each element in nums1.
11        for (int num : nums1) {
12            presenceNums1[num] = 1;
13        }
14      
15        // Mark the presence of each element in nums2.
16        for (int num : nums2) {
17            presenceNums2[num] = 1;
18        }
19      
20        // Array to store the intersection count for nums1 and nums2
21        int[] intersectionCount = new int[2];
22      
23        // Count the number of items in nums1 that are also in nums2.
24        for (int num : nums1) {
25            intersectionCount[0] += presenceNums2[num];
26        }
27      
28        // Count the number of items in nums2 that are also in nums1.
29        for (int num : nums2) {
30            intersectionCount[1] += presenceNums1[num];
31        }
32      
33        // Return the counts as an array of two elements.
34        return intersectionCount;
35    }
36}
37
1#include <vector>
2using std::vector;
3
4class Solution {
5public:
6    // Function to find the count of intersection values in both vectors
7    vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {
8        // Initialize storage for elements' existence, assuming elements range from 0 to 100
9        // No extra space is required as the maximum value is known (100)
10        int existenceNums1[101]{}; // Initialize all elements to 0 for nums1
11        int existenceNums2[101]{}; // Initialize all elements to 0 for nums2
12
13        // Mark the existence of each element from nums1
14        for (int num : nums1) {
15            existenceNums1[num] = 1;
16        }
17
18        // Mark the existence of each element from nums2
19        for (int num : nums2) {
20            existenceNums2[num] = 1;
21        }
22
23        // Vector to store the result, which will hold two values
24        vector<int> intersectionCount(2);
25
26        // Calculate the intersection count for nums1 by checking existence in nums2
27        for (int num : nums1) {
28            intersectionCount[0] += existenceNums2[num]; // If a number exists in nums2, increment the count
29        }
30
31        // Calculate the intersection count for nums2 by checking existence in nums1 
32        for (int num : nums2) {
33            intersectionCount[1] += existenceNums1[num]; // If a number exists in nums1, increment the count
34        }
35
36        // Return the resulting counts as a vector
37        return intersectionCount;
38    }
39};
40
1function findIntersectionValues(nums1: number[], nums2: number[]): number[] {
2    // Initialize two arrays to keep track of the numbers seen in nums1 and nums2.
3    // Assuming the possible number values range between 0 and 100 (inclusive).
4    const seenInNums1: number[] = new Array(101).fill(0);
5    const seenInNums2: number[] = new Array(101).fill(0);
6
7    // Populate the seenInNums1 array based on the values present in nums1.
8    for (const num of nums1) {
9        seenInNums1[num] = 1;
10    }
11
12    // Populate the seenInNums2 array based on the values present in nums2.
13    for (const num of nums2) {
14        seenInNums2[num] = 1;
15    }
16
17    // Initialize an array to keep the count of values found in both nums1 and nums2.
18    // It appears the original intent was to have 2 elements, but the purpose is unclear from the context.
19    // The usage seems incorrect for finding intersection values. 
20    // Instead, let's return a list of unique values which are present in both nums1 and nums2.
21    const intersectionValues: number[] = [];
22
23    // Iterate through the range of possible number values to find common values in nums1 and nums2.
24    for (let i = 0; i <= 100; i++) {
25        if (seenInNums1[i] === 1 && seenInNums2[i] === 1) {
26            // Value i is present in both nums1 and nums2, add it to the intersection array.
27            intersectionValues.push(i);
28        }
29    }
30
31    // Return the array of intersection values.
32    return intersectionValues;
33}
34

Time and Space Complexity

The given code determines the number of intersection values between two lists, nums1 and nums2. The computational complexity is as follows:

Time Complexity

The time complexity of the code is O(n + m), where n is the length of nums1 and m is the length of nums2.

Initially, we convert both lists nums1 and nums2 into sets, which takes O(n) and O(m) time respectively. Then we compute the sum of the boolean expressions checking if each element of nums1 is in s2 and if each element of nums2 is in s1. Both of these operations are done in O(n) and O(m) respectively, since set lookup is O(1) on average. Hence, in total, the time complexity is O(n) + O(m) for both conversions and the sum operations.

Space Complexity

The space complexity of the code is O(n + m) as well. This is because it creates two additional sets from the lists nums1 and nums2, holding up to n and m unique elements respectively, assuming the worst case where all elements in the lists are unique. There is no other significant use of additional space.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄