0

I'm searching the fastest way to find a common item between two lists in Python. These lists have the same length, contain integers (at least 10k) and are unordered. After searched for a while I reached this solution:

def common_item(l1, l2):
    s = None
    l2 = set(l2)
    for i in l1:
        if i in l2:
            s = i
            break

    return s

My goal (if possible) is to improve the code. Any suggestions are welcome.

Edit: I forgot to mention that there is at most one item in common.

oscar0urselli
  • 45
  • 1
  • 7
  • Your algorithm run time is O(len(l)). Just iterating over the lists requires the same amount of run time - therefore you can't improve it. – Guy Tabak Jul 03 '20 at 19:02

3 Answers3

2

This is very inefficient, and it only acquires the first common item in the two lists, not all of them, a better compact solution is by using sets. Like this,

def common_item(l1, l2):
    return list(set(l1).intersection(set(l2)))

OR

def common_item(l1, l2):
    return list(set(l1) & set(l2))

which should return a list of all the elements that are common in the two lists, given that all the elements are unique.

If you have repeated elements in the lists, then you can try this approach which removes the element from the list if you encounter it, at the cost of runtime, which is insignificant when it is small.

def common_item(l1, l2):
    res = []
    for x in l1:
        if x in l2:
            res.append(x)
            l2.remove(x)
    return res
  • Thank you for the answer. However about the fact that I only acquire the first common element, is because I forgot to mention that there is at most one common item. – oscar0urselli Jul 03 '20 at 19:29
  • if this helped you, then you can accept my post as an answer. –  Jul 03 '20 at 19:34
0

def common(list1, list2):

    c = [value for value in list1 if value in list2]

    return c

print(common(list1, list2))
anita
  • 15
  • 4
  • This goes through all items of `list1` even if the goal is to find just 1 common item. Try running this code with list1 with 1,000,000 items, and the 1st item is already a common item. – Gino Mempin May 28 '22 at 06:56
-1

You can find a pythonic approach to this problem at this link.

Example:

a = set([1, 2, 3])
b = set([2, 3, 4])
print(a & b)

Notice how you can use the & operator to represent set intersection.

A time complexity answer for set intersection can be found here

This is linear in the size of the sets, but you also have to convert the lists to sets. However, this is also linear since they are hashtables. another answer here

Chiorean Tudor
  • 198
  • 9