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:
-
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 bothset(nums1)
andset(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
andnums2
into sets. This is done using theset()
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 bothset_nums1
andset_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
andnums2
. 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 EvaluatorExample 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 bothset_nums1
andset_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 bothnums1
andnums2
. 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 ofO(n)
wheren
is the number of elements innums1
. - Converting
nums2
to a set: Similarly, this has a time complexity ofO(m)
wherem
is the number of elements innums2
. - Finding the intersection: The intersection operation
&
for sets is normallyO(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 isO(n)
. - Space for the set of
nums2
: This isO(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.
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
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!