python - Find Largest Element in 2 Ordered Lists which does not occur in one list -

hi i've searched here can't find answer problem.

i'm using python , have 2 lists. both ordered. first list longer 1 (approx 10,000 elements) , never changes. second 1 shorter grows program runs same length.

the lists might this:

[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 10, 11, 12, 13, 16, 18, 19, 20] [1, 1, 2, 2, 3, 4, 16, 18, 19, 20] 

in case, want return 13 because it's maximum element in list 1 not in list 2.

now repeatedly list 1 needs remain unchanged. both lists contain duplicate values.

my naive way of doing far slow:

def removeitems(list2, list1):     list1copy = list(list1)     item in list2:         if item in list1copy:             list1copy.remove(item)      return list1copy  

so create new list , remove items exist in shorter list , value want end value in list1copy.

there must faster way of doing using dicts or something?

so far none of answers have been given take advantage of fact lists ordered , want largest value l1 not in l2. here's solution does:

from itertools import zip_longest # note function named izip_longest in python 2  def max_in_l1_not_in_l2(l1, l2):     if len(l1) <= len(l2):         raise valueerror("l2 has @ least many items l1")     a, b in zip_longest(reversed(l1), reversed(l2), fillvalue=float("-inf")):         if > b:             return         elif != b:             raise valueerror("l2 has larger items l1")     raise valueerror("there no value in l1 not in l2") # should never here 

if can rely upon l2 being proper subset of l1, strip out error checking. if distill down, you'll end simple loop, can become single expression:

next(a a, b in zip_longest(reversed(l1), reversed(l2), fillvalue=float("-inf"))        if > b) 

the reason code faster other implementations (such behzad.nouri's answer using collections.counter) that, reverse iteration, can return result when comes across value l1 not in l2 (the first such value finds largest). doing multiset subtraction process values of both lists, though may need @ largest few values.

here's example should noticeably faster in code in non-short-circuting version:

l1 = list(range(10000000)) l2 = l1[:-1]  print(max_in_l1_not_in_l2(l1, l2)) # prints 9999999