Maximum path sum of 2 lists

Question

My question is about this kata on Codewars. The function takes two sorted lists with distinct elements as arguments. These lists might or might not have common items. The task is find the maximum path sum. While finding the sum, if there any common items you can choose to change your path to the other list.

The given example is like this:

list1 = [0, 2, 3, 7, 10, 12]
list2 = [1, 5, 7, 8]
0->2->3->7->10->12 => 34
0->2->3->7->8      => 20
1->5->7->8         => 21
1->5->7->10->12    => 35 (maximum path)

I solved the kata but my code doesn't match the performance criteria so I get execution timed out. What can I do for it?

Here is my solution:

def max_sum_path(l1:list, l2:list):
    common_items = list(set(l1).intersection(l2))
    if not common_items:
        return max(sum(l1), sum(l2))
    common_items.sort()
    s = 0
    new_start1 = 0
    new_start2 = 0
    s1 = 0
    s2 = 0
    for item in common_items:
        s1 = sum(itertools.islice(l1, new_start1, l1.index(item)))
        s2 = sum(itertools.islice(l2, new_start2, l2.index(item)))
        new_start1 = l1.index(item)
        new_start2 = l2.index(item)
        s += max(s1, s2)
    s1 = sum(itertools.islice(l1, new_start1, len(l1)))
    s2 = sum(itertools.islice(l2, new_start2, len(l2)))
    s += max(s1, s2)
    return s

Answer 1

Your algorithm is actually fast, just your implementation is slow.

The two things that make it take overall O(n²) time:

• l1.index(item) always searches from the start of the list. Should be l1.index(item, new_start1).
• itertools.islice(l1, new_start1, ...) creates an iterator for l1 and iterates over the first new_start1 elements before it reaches the elements you want. So just use a normal list slice instead.

Then it's just O(n log n) for the sorting and O(n) for everything else. And the sorting's O(n log n) is fast, might easily take less time than the O(n) part for any allowed input and even larger ones.

Here's the rewritten version, gets accepted in about 6 seconds, just like the solutions from the other answers.

def max_sum_path(l1:list, l2:list):
    common_items = list(set(l1).intersection(l2))
    if not common_items:
        return max(sum(l1), sum(l2))
    common_items.sort()
    s = 0
    new_start1 = 0
    new_start2 = 0
    s1 = 0
    s2 = 0
    for item in common_items:
        next_start1 = l1.index(item, new_start1)  # changed
        next_start2 = l2.index(item, new_start2)  # changed
        s1 = sum(l1[new_start1 : next_start1])    # changed
        s2 = sum(l2[new_start2 : next_start2])    # changed
        new_start1 = next_start1                  # changed
        new_start2 = next_start2                  # changed
        s += max(s1, s2)
    s1 = sum(l1[new_start1:])                     # changed
    s2 = sum(l2[new_start2:])                     # changed
    s += max(s1, s2)
    return s

Or you could use iterators instead of indexes. Here's your solution rewritten to do that, also gets accepted in about 6 seconds:

def max_sum_path(l1:list, l2:list):
    common_items = sorted(set(l1) & set(l2))
    s = 0
    it1 = iter(l1)
    it2 = iter(l2)
    for item in common_items:
        s1 = sum(iter(it1.__next__, item))
        s2 = sum(iter(it2.__next__, item))
        s += max(s1, s2) + item
    s1 = sum(it1)
    s2 = sum(it2)
    s += max(s1, s2)
    return s

I'd combine the last four lines into one, just left it like you had so it's easier to compare.