Finding an element difference between two lists efficiently

user_12021183 0
Viewed 42

Given the list a and b, where a has one extra element compared to b, I'm trying to locate that extra element that exclusively exists in a in an efficient way. While this could be easily done using set(a) ^ set(b), the problem is that a and b could contain multiple elements with a same name that should be treated independently.

For example:

a = ['Orange', 'Orange', 'Apple', 'Tomato', 'Orange', 'Watermelon']
b = ['Watermelon', 'Orange', 'Tomato', 'Orange', 'Apple']

The result should return the extra 'Orange' that is in list a. My code is:

def ListDiff(a, b):
    for element in a:
        if element in b:
            b.remove(element)
        else:
            solution = element
    return solution

But obviously using the remove() can never be the most efficient and optimized way, especially if a and b are large. Is there an efficient way to locate the extra element?

list python
1 Answers

You can do it in O(n log(n)) time using a sort. After sorting, you can do a linear traversal to find the first difference. Duplicate elements complicate binary search, which would otherwise be possible.

def ldiff(a, b):
    a.sort()
    b.sort()
    for i, j in zip(a, b):
        if i != j:
            break
    else:
        i, j = a[-1], b[-1]
    return i if len(a) > len(b) else j

If you object to the in-place modification preformed by the sort method, use the sorted function instead.

user_29887300
Related