report repair

approach

the expense report is read as a list of integers, and the task is to find entries that add up to 2020 and multiply them. the file keeps several versions side by side, with comments rating them: a naive double loop, a set lookup for the complement, and the one actually used, which sorts the list and walks two pointers inwards.

part 2 needs three entries. it fixes each element in turn and runs the same two-pointer walk on the rest of the list against 2020 - l[i], which makes it O(n²) instead of the naive triple loop that is also left in the file.

the trick

on a sorted list, two pointers find a pair with a given sum in one pass: overshoot moves the right one in, undershoot moves the left one.

def find_two_entries_two_pointers(l, k):
    l = sorted(l)
    left, right = 0, len(l) - 1
    while left < right:
        sm = l[left] + l[right]
        if sm == k:
            return l[left] * l[right]
        elif sm > k: #overshoot, reduce right!
            right -= 1
        else:
            left += 1
    return None