find common items in two lists using for loop python – reduce time complexity

  for-loop, list, python, time-complexity

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?

Source: Python Questions

LEAVE A COMMENT