Two pointers

Binary search used the order of a sorted list to drop half of it at a time. Two pointers use the order in another way: two indexes walk along the data, and at each step the order tells which one to move. Each one only ever moves in one direction, so together they take O(n) steps.

A pair with a given sum

In the step on sets and dicts, you found two values that add up to a target with a set: O(n) time and O(n) memory. If the list is sorted, you can do it with no extra memory. Start left at the smallest value and right at the largest, and look at their sum:

def has_pair(values, target):
    left = 0
    right = len(values) - 1
    while left < right:
        total = values[left] + values[right]
        print(values[left], "+", values[right], "=", total)
        if total == target:
            return True
        if total < target:
            left += 1
        else:
            right -= 1
    return False


print(has_pair([1, 4, 6, 9, 13, 15], 22))

1 + 15 = 16
4 + 15 = 19
6 + 15 = 21
9 + 15 = 24
9 + 13 = 22
True

Why it's right: when the sum is too small, values[left] can't be in any pair. Its biggest possible partner, values[right], isn't enough, and every other partner still in play is smaller. So dropping it loses nothing. In the same way, when the sum is too big, values[right] is too big even with the smallest value still in play. Each round drops one value that can't be in a pair, and after at most n - 1 rounds the pointers meet: O(n) time, O(1) memory. If the list isn't sorted, sorting it first costs O(n log n), and then a set is faster.

Merging two sorted lists

To merge two sorted lists into one, put a pointer at the front of each. The smallest value left is at one of the two pointers, so take the smaller one and move that pointer on. When one list runs out, the rest of the other comes after, already in order:

def merge(a, b):
    result = []
    i = 0
    j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result += a[i:]
    result += b[j:]
    return result


print(merge([2, 5, 8, 9], [1, 5, 7, 12, 15]))

[1, 2, 5, 5, 7, 8, 9, 12, 15]

Every round appends one value, so it's O(n + m) for lists of n and m values. Taking the values with a.pop(0) instead would be O(n) per value, since every value after it moves one place.

Removing duplicates, and a trap

A first try at removing repeats often removes items from a list while a loop goes over the same list. That skips items:

values = [2, 5, 5, 5, 5, 8]
for value in values:
    if values.count(value) > 1:
        values.remove(value)
print(values)

[2, 5, 5, 8]

The loop goes by position. Each remove shifts the later items one place to the left, so the item that moves into the current place is never looked at. It's also O(n²), since count and remove each go through the list.

In everyday Python, you don't remove repeats from the list itself: you make a new list. sorted(set(values)) gives each different value once, in order, in O(n log n). dict.fromkeys(values) makes a dict whose keys are the values, each once, in the order they first appear, so list(dict.fromkeys(values)) drops the repeats and keeps the order, in O(n):

>>> values = [5, 2, 5, 8, 2, 9]
>>> sorted(set(values))
[2, 5, 8, 9]
>>> list(dict.fromkeys(values))
[5, 2, 8, 9]

Interviews ask for the version by hand, when the list itself must change, with O(1) extra memory. For a sorted list, two pointers do it in place: read looks at every value, and write is where the next value to keep goes. A value is new exactly when it differs from the last value kept, values[write - 1]:

def remove_duplicates(values):
    write = 0
    for read in range(len(values)):
        if write == 0 or values[read] != values[write - 1]:
            values[write] = values[read]
            write += 1
    del values[write:]


values = [2, 5, 5, 5, 5, 8, 8, 9]
remove_duplicates(values)
print(values)

[2, 5, 8, 9]

read moves every round and write only when a value is kept, never back: O(n) time and O(1) extra memory. The del at the end cuts off what's left over.