Time limit while finding the duplicates in two lists

Question

First argument is an integer array A of size N.
Second argument is an integer array B of size M.
Return an integer array denoting the common elements.
Input > A = [1, 2, 2, 1], B = [2, 3, 1, 2], out > [1, 2, 2]
Input > A = [2, 1, 4, 10], B = [3, 6, 2, 10, 10], out > [2, 10]

Code is below I got the proper out, but for higher number of elements i m getting errror

    def solve(A, B):
        result = []
        for element in A:
            if element in B:
                result.append(element)
                B.remove(element)
        return result

DO i need to do generator yield functionality for this

@luke why you close the question, its not the same question if you read — Maws, Sep 01 '21 at 05:18

blhsing · Accepted Answer · 2021-09-01T05:40:43.157

2

Membership tests of a list with the in operator cost O(n) in time complexity. You can improve the efficiency by converting the list to a collections.Counter object first to improve the time complexity of membership lookups to O(1):

from collections import Counter

def solve(A, B):
    B = Counter(B)
    result = []
    for element in A:
        if element in B:
            result.append(element)
            B -= {element: 1}
    return result

In fact, collections.Counter offers the intersection operator (&) just for this purpose:

def solve(A, B):
    return list((Counter(A) & Counter(B)).elements())

edited Sep 01 '21 at 05:40

answered Sep 01 '21 at 05:12

blhsing

91,368
6
71
106

A : [ 1, 2, 2, 1 ] B : [ 2, 3, 1, 2 ] Expected out is [1 2 2 ] your out is [1,2] – Maws Sep 01 '21 at 05:16
Oops did not realize that the items can repeat. Updated my answer then. – blhsing Sep 01 '21 at 05:24
TypeError: unsupported operand type(s) for -=: 'int' and 'NoneType' – Maws Sep 01 '21 at 05:27
B -= {element: None} – Maws Sep 01 '21 at 05:27
one question its still o(n) complexity right since we are looping, I got time limit exceed error here also,if i am sending around million records – Maws Sep 01 '21 at 05:31
In this case do i need to write yield functionality – Maws Sep 01 '21 at 05:31
1

No I don't believe converting the function to a generator will improve performance in any way in this case. You can try using the built-in intersection operator of the 'Counter` class, however, which is implemented in a generally more efficient way. I've updated my answer with an example. – blhsing Sep 01 '21 at 05:37

Time limit while finding the duplicates in two lists

1 Answers1