1

Hi I've searched here but can't find an answer to my problem.

I'm using Python and have 2 lists. They are both ordered. The first list is generally the longer one (approx 10,000 elements) and it never changes. The second one is shorter but grows as the program runs to eventually be the same length.

The lists might look like 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 which case, I want to return 13 because it's the maximum element in list 1 that is not in list 2.

Now I do this repeatedly so list 1 needs to remain unchanged. Both lists contain duplicate values.

My naive way of doing it is far too slow:

def removeItems(list2, list1):
    list1Copy = list(list1)
    for item in list2:
        if item in list1Copy:
            list1Copy.remove(item)

    return list1Copy 

So I just create a new list and then remove all the items that exist in the shorter list and then the value I want is the end value in list1Copy.

There must be a much faster way of doing this using dicts or something?

2
  • Does the language matter? If not, then create a hash map of list 1 <Value, No. of times it repeats>, then loop through list 2 and reducing the no. of times value for each. In the end loop through the hashMap's keys and add up the values - O(n)
    – ND27
    Aug 17, 2014 at 21:29
  • 1
    Is list2 a subset of list1? Are they always sorted?
    – zch
    Aug 17, 2014 at 21:29

4 Answers 4

1

So far none of the answers that have been given take any advantage of the fact that the lists are ordered and we want the largest value from l1 that is not in l2. Here's an solution that does:

from itertools import zip_longest # note this function is named izip_longest in Python 2

def max_in_l1_not_in_l2(l1, l2):
    if len(l1) <= len(l2):
        raise ValueError("l2 has at least as many items as l1")
    for a, b in zip_longest(reversed(l1), reversed(l2), fillvalue=float("-inf")):
        if a > b:
            return a
        elif a != b:
            raise ValueError("l2 has larger items than l1")
    raise ValueError("There is no value in l1 that is not in l2") # should never get here

If you can rely upon l2 being a proper subset of l1, you could strip out the error checking. If you distill it down, you'll end up with a very simple loop, which can even become a single expression:

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

The reason this code will often be faster than other implementations (such as behzad.nouri's good answer using collections.Counter) is that, thanks to the reverse iteration, it can return the result immediately when it comes across a value from l1 which is not in l2 (the first such value it finds will be the largest). Doing a multiset subtraction will always process all the values of both lists, even though we may only need to look at the largest few values.

Here's an example that should be noticeably faster in my code than in any non-short-circuting version:

l1 = list(range(10000000))
l2 = l1[:-1]

print(max_in_l1_not_in_l2(l1, l2)) # prints 9999999
1
>>> l1 = [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 10, 11, 12, 13, 16, 18, 19, 20]
>>> l2 = [1, 1, 2, 2, 3, 4, 16, 18, 19, 20]

You can grab a list of all items in l1 that do not occur in l2

>>> filter(lambda i : i not in l2, l1)
[5, 5, 6, 7, 8, 8, 10, 11, 12, 13]

Then take the max of that list

>>> max(filter(lambda i : i not in l2, l1))
13
5
  • 1
    What is the runtime complexity of this algorithm?
    – Matt Ball
    Aug 17, 2014 at 21:24
  • Err... O(N^2)? One N for the filter, second for the max. Aug 17, 2014 at 21:24
  • 1
    That's kind of slow, don't you think?
    – Matt Ball
    Aug 17, 2014 at 21:25
  • I'm sure there's some Python gurus that can do it faster :) that's just the first method that came to mind Aug 17, 2014 at 21:26
  • This gives the incorrect answer. In the above example, the filtered result does not contain a 3, but there were 2 3s in list 1 and only 1 in list 2, so I would want to have 1 of the 3 values left over.
    – davo36
    Aug 17, 2014 at 21:47
1
>>> l1 = [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 10, 11, 12, 13, 16, 18, 19, 20]
>>> l2 = [1, 1, 2, 2, 3, 4, 16, 18, 19, 20]
>>> max(set(l1) - set(l2))
13

edit:

>>> l1 = [19, 20, 20]
>>> l2 = [19, 20]
>>> from collections import Counter
>>> max(Counter(l1) - Counter(l2))
20
3
  • This is very Pythonic, the only problem I'm having with it just now is when list2 = list1 and so max is being applied to an empty sequence...
    – davo36
    Aug 17, 2014 at 21:38
  • In fact, on closer inspection this isn't what I want at all. if say list1 ends with [...19, 20, 20] and list2 ends with [...19, 20] then the answer I want is 20, because one of the 20 values has been removed but not the other. The set operation removes all duplicates and so the number of each value is lost.
    – davo36
    Aug 17, 2014 at 21:43
  • Man than is a very Pythonic answer! Unfortunately it's a bit slower than my code or BlckNght's. Thanks though!
    – davo36
    Aug 20, 2014 at 1:30
0

OK, so I've managed to do it:

def findLargestUnknownLength(l1, l2):

    l1Index = len(l1) - 1
    l2Index = len(l2) - 1

    while True:
        if l2[l2Index] == l1[l1Index]:
            l1Index -= 1
            l2Index -=1
        elif l2[l2Index] < l1[l1Index]:
            return l1[l1Index]

For those wondering, this is part of the solution to The Turnpike Problem. A good description can be found here: Turnpike Walkthrough.

This was a problem on Rosalind.

2
  • This is the same algorithm as in my answer. Note that your code may loop forever if the result comes before the first value in l2 (as you'd get if l1=[1,2,3,4] and l2=[2,3,4], for example). I got around a similar issue by using itertools.zip_longest with negative infinity its fillvalue (though for positive values like you have in the Turnpike problem, -1 would probably do). In your version you might change your loop to while l2Index >= 0 and put return l1[l1Index] at the end, at the same indentation level as the while.
    – Blckknght
    Aug 19, 2014 at 12:56
  • Yep @Blckknght, thanks very much for your solution. I didn't mention it because I didn't know it would be important but yes, l2 is a subset of l1 and this has already been checked. So I've used that one liner of your and it works very slightly quicker than my code, so I've marked yours as the answer. Thanks very much.
    – davo36
    Aug 20, 2014 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.