349. Intersection of Two Arrays

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:

1. Since each element in the result must be unique, using a set data structure is a natural choice because sets automatically remove duplicate elements.

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

3. 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).

4. 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:

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

   1set_nums1 = set(nums1)
   2set_nums2 = set(nums2)

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

   1intersection_set = set_nums1 & set_nums2

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

   1result_list = list(intersection_set)

4. 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:

1return 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.

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.

  1set_nums1 = set([1, 2, 2, 1]) => {1, 2}
  2set_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.

  1intersection_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.

  1result_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

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.

1. Converting nums1 to a set: This operation has a time complexity of O(n) where n is the number of elements in nums1.
2. Converting nums2 to a set: Similarly, this has a time complexity of O(m) where m is the number of elements in nums2.
3. 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:

1. Space for the set of nums1: This is O(n).
2. 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.