I was asked to find common items between two lists in Python during an interview. I provided three solutions: using set.intersection, list comprehension and for loop. Below is the for loop I did:

def common_elements(list1, list2):
    result = []
    for element in list1:
        if element in list2:
            result.append(element)
    return result

After I did the for loop the interviewer asked me if there is any way to reduce the time complexity by not having to going through every item in the list. He also hinted I can sort the list first. I wasn't able to answer that question and I am still struggling with it. How can I approach this question?

CodePudding user response：

You can combine a for-loop and an iterator to traverse the sorted lists in parallel and yield matches along the way.

def common(L1,L2):
    iter2 = iter(sorted(L2)) # iterator on sorted L2 values
    Done  = object()         # flag to identify end of iteration
    v2    = next(iter2,Done) # get first (lowest) element of L2
    for v1 in sorted(L1):
        while v2 is not Done and v2<v1:
            v2 = next(iter2,Done) # advance in sorted L2 to reach or surpass v1
        if v1 == v2: 
           yield v1               # return matches
           v2 = next(iter2,Done)  # advance (only match items once each)
        if v2 is Done: break      # stop if L2 values exausted


for c in common([3,7,4,2,4,3,1],[4,5,2,2,4,3]):
    print(c)
2
3
4
4

This will have a time complexity of O(NlogN MlogM) instead of O(N*M) where N and M are the list sizes

Another solution you could have proposed is to use the Counter class which would have a complexity of O(N M):

from collections import Counter
L1,L2 = [3,7,4,2,4,3,1],[4,5,2,2,4,3]
c = list((Counter(L1) & Counter(L2)).elements())
print(c) # [3, 4, 4, 2]

CodePudding user response：

As I mentioned in the question comments, neither sets nor your loop solution can handle duplicates in each list, so I'll assume it's guaranteed that there aren't any.

Here's a generator version that sorts both lists and then merges them (using heapq.merge). That way, values common to both lists appear together, so we yield a value if it's the same as the previous:

def common_elements1(list1, list2):
    list1.sort()
    list2.sort()
    merged = merge(list1, list2)
    prev = next(merged, None)
    for x in merged:
        if x == prev:
            yield x
        prev = x

A hackish walrus list comp version:

def common_elements2(list1, list2):
    list1.sort()
    list2.sort()
    merged = merge(list1, list2)
    prev = next(merged, None)
    return [x for x in merged
            if x == prev or not [prev := x]]

Or with itertools.groupby:

def common_elements3(list1, list2):
    list1.sort()
    list2.sort()
    merged = merge(list1, list2)
    return [x for _, [_, *g] in groupby(merged)
            for x in g]

All code with tests: Try it online!

CodePudding user response：

I believe the answer to your question is double pointer

The idea is to sort the two lists and have a pointer i starting at the beginning of l1 and j at the beginning of l2, each time you compare the two elements and you move the pointer of the smallest element forward, until one of them reaches the end.

def findCommon(l1,l2):
    l1.sort()
    l2.sort()
    i= 0
    j = 0
    res = []
    while i < len(l1) and j < len(l2):
        if l1[i] == l2[j]:
            res.append(l1[i])
        if l1[i] < l2[j]:
            i  = 1
        else:
            j  = 1
    return res