LeetCode Python Solutions: 350. Intersection of Two Arrays II
ZeroStress LeetCode Pythons Solution: 350. The intersection of Two Arrays II #python #leetcode
https://leetcode.com/problems/interse...
Twitter: / qiaoliuciao
Key Learnings:
Understanding Dictionaries (Hash Maps):
The hashMap is a dictionary (or hash map) that stores the counts of elements from nums1.
A dictionary is a data structure that maps keys to values. In this case, the keys are the elements from nums1, and the values are the counts of each element.
The hashMap.get(key, default) method is used to retrieve the value associated with a given key. If the key is not present in the dictionary, it returns the default value (in this case, 0).
Counting Elements in nums1:
The first loop iterates over each element (num) in nums1.
The line hashMap[num] = hashMap.get(num, 0) + 1 updates the count of num in the hashMap dictionary.
If num is already a key in hashMap, hashMap[num] retrieves the current count and increments it by 1.
If num is not present in hashMap, hashMap.get(num, 0) returns 0 as the default count, and then 1 is added to it.
Finding Intersection in nums2:
The second loop iterates over each element (num) in nums2.
The line if num in hashMap and hashMap[num] != 0 checks if num exists as a key in hashMap and its count is non-zero.
If num is present in hashMap and its count is non-zero, it means num is a common element between nums1 and nums2.
If the condition is satisfied, num is appended to the result list, indicating its presence in the intersection.
Additionally, the count of num in hashMap is decremented by 1 to account for its occurrence in the intersection.
Returning the Intersection:
The result list contains the elements that appear in both nums1 and nums2 with the correct multiplicities.
After iterating over all elements in nums2, the result list is returned as the final intersection.
The algorithm behind Solution 2 is as follows:
Create a hash map (hashMap) to store the counts of elements in nums1.
Traverse nums1 and update the counts in the hashMap.
Traverse nums2 and check if each element exists in hashMap with a non-zero count.
If a common element is found, append it to the result list and decrement its count in hashMap.
Finally, return the result list, which represents the intersection of the two arrays.
By understanding the use of dictionaries (hash maps) and the logic of counting elements and finding the intersection, you'll gain a solid foundation for approaching similar problems and understanding more complex algorithms.
The approach of the solution can be summarized as follows:
Initialize an empty hash map (hashMap) and an empty result list (result).
Iterate over each element (num) in nums1:
Check if num already exists as a key in the hashMap using the in operator.
If num exists, increment its count in the hashMap by 1 using hashMap[num] = hashMap.get(num, 0) + 1.
If num does not exist, add it to the hashMap with an initial count of 1.
Iterate over each element (num) in nums2:
Check if num exists as a key in the hashMap and its count is non-zero (greater than 0).
If both conditions are satisfied, it means num is a common element between nums1 and nums2.
Append num to the result list and decrement its count in the hashMap by 1 using hashMap[num] -= 1.
Return the result list, which contains the elements that appear in both nums1 and nums2 with the correct multiplicities.
The approach of the solution can be broken down into the following steps:
Count the occurrences of each element in nums1 using a hash map (hashMap).
Traverse nums2 and check if each element exists in hashMap and has a non-zero count.
If a common element is found, add it to the result list and decrement its count in hashMap.
Return the result list containing the intersection of the two arrays.
This approach efficiently handles cases with duplicate elements and ensures that the intersection includes elements with the correct multiplicities. By leveraging a hash map to track the counts, we can accurately determine the common elements between the two arrays and their respective multiplicities.
00:00 Code
03:10 Solution
13:00 End