349. Intersection of Two Arrays

EasyArrayHash TableTwo PointersBinary SearchSorting

Problem Description

The problem requires us to find the intersection of two integer arrays, nums1 and nums2. The intersection of two arrays means the elements that are common to both arrays. However, there are some special rules in this problem:

Each element in the resulting array must be unique, which means if an element appears more than once in the intersection, it should only appear once in the result.
The result can be returned in any order, so there is no need to sort the result or follow the order of any of the input arrays.

The goal is to write a function that takes these two arrays as input and returns a new array that satisfies these conditions.

Intuition

To arrive at the solution, we need to think about the most efficient way to find common elements between the two given arrays. Here are a few key points to consider:

Since each element in the result must be unique, using a set data structure is a natural choice because sets automatically remove duplicate elements.
To find the common elements, we can convert both arrays into sets and then find the intersection of these sets. The intersection operation is well defined in mathematics and programming languages as the set of elements that are present in both sets.
The intersection operator in Python (denoted by &) conveniently does this job for us, returning another set that contains only the elements that are found in both set(nums1) and set(nums2).
After we get the intersection, its elements are unique by the definition of a set. However, since the final output requires the result to be a list, we convert this intersection set back to a list using the list() function.

The combination of these steps provides us with a simple and elegant solution to the problem, which is both easy to code and understand.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The implementation of the solution uses a set intersection approach, leveraging Python's built-in set operations. Here is a step-by-step walkthrough of the algorithm and the associated data structures or patterns used:

Convert lists to sets: The first step is to convert the two input lists nums1 and nums2 into sets. This is done using the set() function in Python. The purpose of this conversion is two-fold: to eliminate any duplicate elements within each array and to prepare the data for set-based operations.
```
set_nums1 = set(nums1)
set_nums2 = set(nums2)
```
Intersect the sets: Once we have two sets, we can find their intersection. In Python, the intersection of two sets can be found using the & operator. This operation will return a new set containing only the elements that are present in both set_nums1 and set_nums2.
```
intersection_set = set_nums1 & set_nums2
```
Convert the set back to a list: After finding the intersection, we have a set of unique elements that are present in both input arrays. Since the problem requires the result to be returned as a list, the final step is to convert this set back into a list. We can do this simply by passing the set to the list() constructor.
```
result_list = list(intersection_set)
```
Return the result: The result now contains all the unique elements that are present in both nums1 and nums2. This list is returned as the final output of the function.

By succinctly combining these steps within the intersection method of the Solution class, the entire process is captured in a single, readable line of code:

return list(set(nums1) & set(nums2))

This one-liner showcases the power and simplicity of Python for solving such problems, where the language's built-in data structures and operators do much of the heavy lifting for us.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example.

Suppose we have two integer arrays: nums1 = [1, 2, 2, 1] and nums2 = [2, 2, 3].

Convert lists to sets: As per the first step, we convert these lists into sets to eliminate any duplicates.

set_nums1 = set([1, 2, 2, 1]) => {1, 2}
set_nums2 = set([2, 2, 3]) => {2, 3}

Intersect the sets: Now, we find the intersection of these two sets to identify the common elements. The & operator helps us with this.
```
intersection_set = {1, 2} & {2, 3} => {2}
```
After this step, intersection_set holds the unique elements that are present in both set_nums1 and set_nums2, which in this case is the single element {2}.
Convert the set back to a list: We then convert the resulting set back into a list since the function is expected to return a list.
```
result_list = list({2}) => [2]
```
Return the result: The final resulting list [2] contains all the unique intersection elements from both nums1 and nums2. This is the output we would return from the function.

By applying the solution approach to this example, we successfully identified the intersection of two arrays with duplicate elements, reduced them to their unique elements, and provided the required list output. The elegance of Python's set operations made this process straightforward and efficient. Applying this same approach to the question at hand, the function returns the list [2] as the intersection between nums1 and nums2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
5        # Convert the first list to a set to eliminate duplicates
6        set_nums1 = set(nums1)
7      
8        # Convert the second list to a set to eliminate duplicates
9        set_nums2 = set(nums2)
10      
11        # Find the intersection of the two sets, which contains only the common elements
12        intersection_set = set_nums1 & set_nums2
13      
14        # Convert the resulting set to a list before returning
15        return list(intersection_set)
16
17# The code defines a method intersection within the Solution class that takes two lists of integers
18# and returns a list of the unique elements that are present in both lists.
19

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    // Finds the intersection of two arrays, i.e., elements that appear in both arrays.
6    public int[] intersection(int[] nums1, int[] nums2) {
7        // Initialize a boolean array to track which elements from nums1 have been seen.
8        boolean[] seen = new boolean[1001]; // Assumes the elements are in the range [0, 1000].
9      
10        // Mark elements present in nums1 as seen.
11        for (int num : nums1) {
12            seen[num] = true;
13        }
14      
15        // Use a list to collect the intersection elements.
16        List<Integer> intersectionElements = new ArrayList<>();
17      
18        // Iterate over nums2 to find common elements.
19        for (int num : nums2) {
20            // If an element from nums2 has been seen and is not yet included in the intersectionElements.
21            if (seen[num]) {
22                intersectionElements.add(num); // Add the element to the intersection list.
23                seen[num] = false; // Mark it as not seen to avoid duplicates in the intersectionElements.
24            }
25        }
26      
27        // Convert the List of Integer to an array of int for the result.
28        int[] result = new int[intersectionElements.size()];
29        for (int i = 0; i < intersectionElements.size(); i++) {
30            result[i] = intersectionElements.get(i);
31        }
32      
33        // Return the result array containing the intersection of the two arrays.
34        return result;
35    }
36}
37

1#include <vector>
2#include <cstring> // Required for memset function
3
4class Solution {
5public:
6    // Computes the intersection of two vectors, nums1 and nums2,
7    // and returns the unique elements present in both.
8    std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
9        // Create an array to mark the presence of elements.
10        // Assuming the elements in nums1 and nums2 are in the range [0, 1000]
11        bool seen[1001];
12        std::memset(seen, false, sizeof(seen)); // Initialize all elements in 'seen' to 'false'
13
14        // Mark all elements present in nums1 in the 'seen' array
15        for (int num : nums1) {
16            seen[num] = true;
17        }
18      
19        // Vector to store the intersection result
20        std::vector<int> result;
21      
22        // Iterate through nums2 to find common elements,
23        // add them to result and mark them as 'false' in 'seen' to avoid duplicates
24        for (int num : nums2) {
25            if (seen[num]) {
26                result.push_back(num); // If element is seen, add to result
27                seen[num] = false;     // Set to 'false' to avoid adding duplicates
28            }
29        }
30
31        // Return the vector containing the intersection of nums1 and nums2
32        return result;
33    }
34};
35

1/**
2 * Finds the intersection of two arrays, meaning the elements that are present in both arrays.
3 * The function assumes the numbers in both arrays are integers and within the range of 0 to 1000.
4 * 
5 * @param {number[]} nums1 - First array of numbers.
6 * @param {number[]} nums2 - Second array of numbers.
7 * @return {number[]} - Array containing the intersection of both input arrays.
8 */
9const intersection = (nums1: number[], nums2: number[]): number[] => {
10    // Initialize a boolean array with a fixed size of 1001,
11    // corresponding to the specified range of numbers.
12    const seen: boolean[] = new Array(1001).fill(false);
13  
14    // Mark the numbers that are present in the first array as true in the 'seen' array.
15    for (const number of nums1) {
16        seen[number] = true;
17    }
18  
19    // Initialize the array that will hold the intersection result.
20    const result: number[] = [];
21  
22    // Traverse the second array and check if the current number is seen.
23    // If it is, add it to the result and set its 'seen' value to false
24    // to prevent duplicates if it appears again in nums2.
25    for (const number of nums2) {
26        if (seen[number]) {
27            result.push(number);
28            seen[number] = false;
29        }
30    }
31  
32    // Return the resultant array containing the intersection of nums1 and nums2.
33    return result;
34};
35
36// Example usage:
37// const nums1 = [1, 2, 2, 1];
38// const nums2 = [2, 2];
39// const result = intersection(nums1, nums2); // result would be [2]
40

Time and Space Complexity

Time Complexity

The time complexity for the given solution involves two main operations: converting the lists to sets and finding the intersection of these sets.

Converting nums1 to a set: This operation has a time complexity of O(n) where n is the number of elements in nums1.
Converting nums2 to a set: Similarly, this has a time complexity of O(m) where m is the number of elements in nums2.
Finding the intersection: The intersection operation & for sets is normally O(min(n, m)) because it checks each element in the smaller set for presence in the larger set.

Thus, the overall time complexity can be summarized as O(max(n, m)) assuming that the intersection operation is dominated by the process of converting the lists to sets.

Space Complexity

The space complexity considers the additional space required besides the input:

Space for the set of nums1: This is O(n).
Space for the set of nums2: This is O(m).

Since these sets do not depend on each other, the total space complexity is O(n + m) for storing both sets.

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

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

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know