1

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].

Improve this question
2
  • @mkrieger1 I have kept the longer array's (nums2) all elements in ht. Commented Nov 16, 2021 at 10:28
  • I'm voting to close this question as duplicate of If x is a value in this dict Commented Nov 16, 2021 at 10:36

4 Answers 4

Reset to default
2

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
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Thank you for pointing out the values part. Doing that I can't pass for nums1 as [3,1,2] nums2 as [1,1]. Since both, arrays have only one 1. the expected output is [1]. However, mine is [1,1]. How do I check this?
you could apply a set(intersection) to remove the duplicate
I changed ht to set using ht = set() and still couldn't pass for nums1 as [3,1,2] nums2 as [1,1]. Still the output is same.
IF you change your return to return list(set(intersection)) does it give you the correct answer of [1] ?
then it will fail for the conditions where there are two elements in both arrays. Eg. Input: [1,2,2,1] [2,2], Expected Output: [2,2]. My output[2]
|
1

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
Improve this answer

2 Comments

Thank you for pointing out the valid points. This is insightful. Also, would you please mention the effect of using Counter in space and time complexity? Would counter contribute to the time and space complexity?
I don't know the underlying code, but it should be O(n) and using the same space as the resulting dictionnary. Also, it has some C implementation or something, because it's faster that doing the dictionnary by yourself. (I remember some blog post that compared ways to count, and Counter was close to, if not, the best)
1

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.

Improve this answer

1 Comment

List comprehension is interesting. Thank you for suggesting, will look into this!
0

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())
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.