1 minute read

350. Intersection of Two Arrays II

Difficulty: Easy

Related Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

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] Explanation: [9,4] is also accepted.

First Attempt:

Code:

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        numdict={}
        for i in nums1:
            if i in nums2:
                if i in numdict:
                    numdict[i]+=1
                else:
                    numdict[i]=1
                nums2.remove(i)
        numlist=[]
        for i in numdict:
            for j in range(numdict[i]):
                numlist.append(i)
        return numlist

Feedbacks:

I compared two lists and if there’s common element, I added it to dictionary. And them appended to the list and returned that list. Time Complexity is O(n^2). Needs to be improved.

Second Attempt:

Code:

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) > len(nums2): return self.intersect(nums2, nums1)
            
        cnt = Counter(nums1)
        ans = []
        for x in nums2:
            if cnt[x] > 0:
                ans.append(x)
                cnt[x] -= 1
        return ans

Feedbacks:

I can use Counter built-in function to create a dictionary for nums1 elements. It automatically creates me a dictionary with keys and values. So I loop around nums2 and if there is common element in dictionary and nums2, I append it to new ans list. And return ans list at last which gives me the answer.

You may also enjoy