I am practicing leetcode. Here is the question. https://leetcode.com/problems/intersection-of-two-arrays-ii/:

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.

Where I am doing the mistake?

def intersect(nums1: List[int], nums2: List[int]) -> List[int]:
    ht = dict()
    length1 = len(nums1)
    length2 = len(nums2)
    longer = []
    smaller = []
    intersection = []
    if length1 > length2:
        longer = nums1
        smaller = nums2
    else:
        longer = nums2
        smaller = nums1
    
    for i in range(len(longer)):
        ht[i] = longer[i]
        
    for j in range(len(smaller)):
        if smaller[j] in ht:
            intersection.append(smaller[j])
        else:
            j  = 1
    return intersection

The answer is accepted for

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

However, it fails for

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

My output is [4].

CodePudding user response：

The problem is you are checking if smaller[j] in ht which will by default check that each smaller[j] is in the keys of ht. The keys are ht you set to the indexes of the longer array.

You could just replace with if smaller[j] in ht.values(), but you could just do away with ht dict and achieve it by checking if smaller[j] is in longer.

However, the current approach doesn't work, as comparing from longest to smallest will always be flawed as the longest may have [1,1] and the shortest just [1], or in reverse, so you would always achieve a different result.

Here is another solution that counts the values in each list. Then it will iterate through the keys of both and any in common, it will take the min value and multiple this by the key to give you the result. eg. if you had [1,2,2,1] and [2,2], then 2 = 2 in both list counts. Resulting in a min count of 2, multiplied by the key 2 would give you an output of [2,2].

See below;

def intersect(nums1: List[int], nums2: List[int]) -> List[int]:
    ht1 = dict()
    ht2 = dict()
    intersection = []
    
    for num1 in nums1:
        ht1[num1] = ht1[num1]   1 if num1 in ht1 else 1
        
    for num2 in nums2:
        ht2[num2] = ht2[num2]   1 if num2 in ht2 else 1

    for key in ht2.keys():
        if key in ht1:
            intersection  = key * [min([ht2[key],ht1[key]])]
        
    return intersection

CodePudding user response：

TL;DR: There are several stuffs that seems wrong to me, that I detail later.

My biggest advice is that, in this function, you have two steps "count number in list" and "calc intersection of lists". You should code them separately, make some test cases to check that it works, then run the whole loop. (With these test cases, you'll quickly find what went wrong)

What seems wrong to me:

1)

for i in range(len(longer)):
    ht[i] = longer[i]

Here, I imagine you'd like to count the number of instances. For example, if nums1 = [5, 8, 8], you'd like a dict {5: 1, 8: 2}

It's not what your loop is doing. It's saying what number was at which index (your loop returns {1: 5, 2: 8, 3: 8})

And it's not very pythonic to do "for i in range(len(list))". You should do:

for number in in longer:
   ht[number] = ht.get(number, 0)   1

for j in range(len(smaller)):
    if smaller[j] in ht:
        intersection.append(smaller[j])
    else:
        j  = 1

Why would you increase your index j ? Also, you need to reduce hf[number[j]] when you encounter it

for number in smaller:
    if ht.get(number, 0) > 0:
        intersection.append(number)
        ht[number] -= 1

What I would code

from collections import Counter

 def calc_intersect(nums1, nums2):
     num_to_count_1 = Counter(nums1)
     intersect = []
     for num in nums2:
         if num_to_count_1[num] > 0:
             intersect.append(num)
             num_to_count_1[num] -= 1
     return intersect

CodePudding user response：

I would suggest to use list comprehension which is a very fast tool. Then the code would be

intersect1 = [el for el in nums1 if el in nums2]
intersect2 = [el for el in nums2 if el in nums1]

if len(intersect1) < len(intersect 2):
    result = intersect1
else:
    result = intersect2

You need to compute two intersect lists to get the correct result. The smaller intersect list is the correct one.

CodePudding user response：

You've made it more complicated than it really is. Try this:

class Solution():
    def __init__(self, a, b):
        self.a = a
        self.b = b
    def intersect(self):
        return [x for x in self.a if x in self.b]
    
print(Solution([4,9,5],[9,4,9,8,4]).intersect())