Intersection Of Two Arrays Ii - Leetcode Solution

Problem Statement:

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9]

Solution:

We can solve this problem using a hashmap. We can create a hashmap to store the frequency of each element in nums1. We can then go through nums2 and check if each element is in the hashmap. If the element is in the hashmap, we can add it to the result and update the frequency of the element in the hashmap. If the frequency of the element in the hashmap is 0, we can remove the element from the hashmap. We continue this process until we have gone through all the elements in nums2.

Time Complexity: O(n)

Space Complexity: O(n)

Here is the python code for the solution:

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        d = {}
        for num in nums1:
            if num in d:
                d[num] += 1
            else:
                d[num] = 1
        
        res = []
        for num in nums2:
            if num in d and d[num] > 0:
                res.append(num)
                d[num] -= 1
                if d[num] == 0:
                    del d[num]
        
        return res

We create a dictionary 'd' to store the frequency count of each element in nums1. We then create an empty list 'res' to store the results. We loop through the elements in nums2 and check if the element is in the dictionary and if its frequency is greater than 0. If it is, we add the element to 'res', decrement its frequency in the dictionary, and delete it if its frequency becomes 0. Finally, we return the 'res' list as the result.

1