350. Intersection of Two Arrays II

Problem Description

The problem provides us with two integer arrays, nums1 and nums2, and asks us to find the intersection of these two arrays. The intersection consists of elements that appear in both arrays. If an element occurs multiple times in both arrays, it should appear in the final result as many times as it is common to both. The result can be returned in any order.

To elaborate, we need to identify all the unique elements that the two arrays have in common. Then, for each unique element found in both arrays, we need to include that element in our result array as many times as it occurs in both. For example, if the number 3 appears twice in nums1 and four times in nums2, it should appear twice in the intersection array since that's the minimum count between the two arrays.

Intuition

The foundation of the solution is to count the frequency of each element in the first array, which is nums1. We then iterate through the second array, nums2, checking if the elements appear in the counter we created from nums1. If an element from nums2 is found in the counter and has a count greater than zero, it is part of the intersection. We add this element to the result list and decrease its count in the counter by one to ensure that we don't include more occurrences of an element than it appears in both arrays.

Here’s how we arrive at the solution step by step:

1. Count Elements of nums1: By creating a counter (a specific type of dictionary) for nums1, we efficiently track how many times each element occurs.

2. Iterate Over nums2 and Collect Intersection: We go through each element in nums2. If the element is found in the counter with a non-zero count, this indicates that the element is both in nums1 and nums2.

3. Add to Result and Update Counter: For every such element found, we add it to our result list and then decrement the count for that element in the counter to ensure we only include as many instances as are present in nums1.

The above steps are simple and use the property of counters to help us easily and efficiently find the intersection of the two arrays.

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

Solution Approach

The implementation of the solution makes use of the following concepts:

• Counter (from collections module): This is used to construct a hash map (dictionary) that counts the frequency of each element in nums1. It's a subclass of a dictionary which is specifically designed to count hashable objects.

The code implementation goes as follows:

1. We start by importing Counter from the collections module.

   1from collections import Counter

2. We then use Counter to create a frequency map of all the elements present in nums1.

   1counter = Counter(nums1)

3. We initialize an empty list res which will hold the elements of the intersection.

   1res = []

4. Next, we iterate over each element num in nums2. During each iteration, we perform the following actions:

   • Check if num exists in the counter and its count is greater than 0. This confirms whether num should be a part of the intersection.

     1if counter[num] > 0:

   • If the above condition is true, we append num to our res list. This adds num to our intersection list.

     1res.append(num)

   • Then we decrement the count of num in the counter by one to ensure we do not include it more times than it appears in nums1.

     1counter[num] -= 1

5. Finally, once we've completed iterating over nums2, we return the res list which contains the intersection of nums1 and nums2.

   1return res

The choice of Counter and the decrementing logic ensures that each element is counted and included in the result only as many times as it is present in both input arrays. This method is efficient because creating a counter is a linear operation (O(n)) and iterating through the second list is also linear (O(m)), where n and m are the sizes of nums1 and nums2 respectively. The conditional check and decrement operation during the iteration are constant time (O(1)) since hash map access is in constant time.

Example Walkthrough

Let's use a small example to illustrate the solution approach. Assume we have the following two arrays:

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

We want to find the intersection of these two arrays.

Following the described solution approach:

1. Counter is used to create a frequency map for nums1. After this step, we have:

   1counter = Counter([1,2,2,1])
   2# counter = {1: 2, 2: 2}

   The counter represents that the number 1 appears twice and the number 2 appears twice in nums1.

2. We initialize an empty list res to store the intersection.

   1res = []

3. We iterate over each element in nums2.

   a. First, we check if 2 (the first element of nums2) exists in counter and has a count greater than 0.

   Since counter[2] is indeed greater than 0, we append 2 to our res list. Then, we decrement the count of 2 in the counter by one to reflect the updated count.

   1res.append(2)
   2counter[2] -= 1
   3# Now, counter = {1: 2, 2: 1}

   b. We move to the next element which is again 2. We perform the same check and find that counter[2] is still greater than 0. So, we append this 2 to res and again decrement the counter for 2.

   1res.append(2)
   2counter[2] -= 1
   3# Finally, counter = {1: 2, 2: 0}

Since there are no more elements in nums2 to iterate over, our res list currently looks like this:

1res = [2, 2]

4. We return the res list which is [2, 2] as the final result. This reflects the intersection of nums1 and nums2, indicating that the element 2 appears in both arrays and does so exactly twice, which is the minimum number of times it appears in any one array.

The final intersection array is [2, 2], and it is derived through the efficient counting and iteration method described in the solution approach.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed in two parts:

1. Building a counter from nums1 takes O(n) time, where n is the length of nums1, as each element is processed once.
2. Iterating over nums2 and updating the counter takes O(m) time, where m is the length of nums2, as each element is processed once.

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

Space Complexity

The space complexity of the code depends on the space used by the counter data structure:

1. The counter keeps track of elements from nums1, therefore it uses O(n) space, where n is the unique number of elements in nums1.

2. The res list contains the intersected elements. In the worst case, if all elements in nums2 are present in nums1, it can take O(min(n, m)) space, where n is the length of nums1 and m is the length of nums2.

Taking both into account, the space complexity is O(n + min(n, m)) which simplifies to O(n) as min(n, m) is bounded by n.

Overall, the space complexity of the code is O(n) where n represents the number of unique elements in nums1.

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