Two Ends of a Sorted List

In the last module a set remembered what had gone past, and a pair was found in one pass. That costs memory: the set can grow as large as the list. When the list is sorted, there is a way to find a pair that remembers nothing at all. It keeps two positions, one at each end, and moves them towards each other. The method is short, and the reason it is correct is the real subject of this module: each move throws away part of the problem, and you have to be sure that the answer was not in the part thrown away.

Before this, you can: find a pair in one pass with a set or a dictionary; sort a list, and say what sorting leaves alone; loop while a condition holds, and count the work by asking what each step rules out.

By the end you will be able to say what a sorted list lets you conclude from one comparison, walk two positions inward, argue that nothing is missed, decide when sorting first is worth it, walk two sorted lists together, and rearrange a list in place with a reader and a writer.

Before you read on, decide what this prints:

prices = [2, 4, 7, 11, 15]
print(prices[0] + prices[4], prices[1] + prices[4], prices[0] + prices[3])

17 19 13

The smallest price with the largest gives 17. Change the smaller one for the next price up and the total can only rise: 19. Change the larger one for the next price down and it can only fall: 13. Nothing was searched for. Because the list is sorted, you knew which way each total would go before working it out.

What sorted gives you

In a sorted list, the item to the right of any item is at least as large, and the item to its left is at least as small. So for a pair of positions, one near the left and one near the right:

• moving the left position one step to the right can only make the total larger, or leave it the same;
• moving the right position one step to the left can only make the total smaller, or leave it the same.

That is all the method uses. If a total is too large, there is exactly one move that can help: bring the right position in. If it is too small, bring the left position in. You never have to wonder which.

One position at each end

To decide whether two items of a sorted list add up to a target, start with the widest pair there is, the first item and the last, and let the comparison choose the move.

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

print(has_pair_sorted([2, 4, 7, 11, 15], 18), has_pair_sorted([2, 4, 7, 11, 15], 12))

True False

Follow the first call, with a target of 18. The ends are 2 and 15: 17, too small, so the left position moves in. Now 4 and 15: 19, too large, so the right moves in. Now 4 and 11: 15, too small; left moves. Now 7 and 11: 18. Found.

The loop runs while left < right. When the two positions meet there is only one item between them, and one item is not a pair. That condition is also what stops an item being paired with itself.

Each turn of the loop moves one position one step, and the positions start n − 1 apart, so there are at most n − 1 turns. No set, no dictionary: two numbers are all it remembers.

Why nothing is missed

A method that skips most of the pairs needs an argument that the pair it wanted was not among the ones it skipped. Here is the argument, and it is worth being able to give it yourself.

Take the first step above: 2 and 15 make 17, which is too small for 18. The left position moves, and the 2 is never looked at again. That discards every pair that contains the 2: with 4, with 7, with 11. Was that safe? The 2 has just been tried with 15, the largest partner it could possibly have, and even that was too small. With any other partner the total would be smaller still. So no pair containing the 2 can reach the target. Discarding it loses nothing.

The other move is the mirror image. If the total is too large, the right-hand item has just been tried with the smallest partner available to it and was still too large. With any other partner it would be larger still. It can go.

So at every moment, this is true: if a pair that adds up to the target exists, both of its items are still between the two positions, ends included. It is true at the start, when the positions are at the two ends. Each move keeps it true, by the argument above. When the positions meet and nothing has been found, there is no room left for a pair, so there was none.

A statement like that, true before the loop and kept true by every turn, is called an invariant. It is how you know a loop is right without trying every input.

When the list is not sorted

Everything above rests on the list being sorted. On an unsorted list a total that is too small tells you nothing about which way to move, and the method will walk straight past a pair.

You can always sort first. That has two costs.

Sorting is not free. It takes more work than one pass, though far less than comparing every pair. As a rough guide, sorting n items takes in the order of n times the number of halvings of n: for a thousand items that is about ten thousand comparisons at worst, where every pair would be half a million. (Python's sort does better on a list that is already partly in order, and how long a comparison takes depends on what is being compared.) So "sort, then two positions" sits between the set method, which reads the list once, and the two loops.

And sorting loses the positions. After sorted, the 7 that was at position 4 may be at position 2, and nothing says where it came from.

prices = [11, 2, 15, 4, 7]
in_order = sorted(prices)
print(in_order, has_pair_sorted(in_order, 18))
print(in_order.index(7), prices.index(7))

[2, 4, 7, 11, 15] True
2 4

If the question is "is there a pair?" or "what are the two values?", sort and go. If the question is "at which positions of the original list?", sorting has thrown away what you were asked for, and the dictionary of the last module is the better tool. Choosing between the two methods is choosing what you can afford to lose: memory, or the original order.

Two lists, a position in each

The same idea works across two sorted lists. To merge them into one sorted list, keep a position in each. The smaller of the two items at those positions is the smallest item not yet taken, so take it and move that position on.

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

print(merge([1, 4, 9], [2, 3, 10, 12]))

[1, 2, 3, 4, 9, 10, 12]

The first loop runs while both lists have something left. When one runs out, whatever remains of the other is already in order and larger than everything taken, so the last two loops copy it across. At most one of them does anything. Forgetting them is the usual mistake: the answer comes out right whenever the lists happen to end together, and short otherwise.

Each turn of the first loop compares the two front items once and takes one of them, so there are never more comparisons than there are items in the two lists together. An item may be compared more than once: above, the 4 is compared with 2, then with 3, and then with 10, when it is at last the smaller and is taken. What cannot happen is a comparison that takes nothing.

A reader and a writer

Two positions can also move in the same direction along one list. One reads every item. The other marks where the next item worth keeping should be written. The writer never gets ahead of the reader, so nothing is overwritten before it has been read.

Here is a sorted list with repeats, squeezed in place so that each value appears once at the front:

def squeeze(values):
    if len(values) == 0:
        return 0
    write = 1
    for read in range(1, len(values)):
        if values[read] != values[write - 1]:
            values[write] = values[read]
            write = write + 1
    return write

numbers = [3, 3, 5, 5, 5, 8, 9, 9]
kept = squeeze(numbers)
print(kept, numbers[:kept], numbers)

4 [3, 5, 8, 9] [3, 5, 8, 9, 5, 8, 9, 9]

The function returns how many items were kept, and the list's first four places now hold them. What lies after the writer is leftovers: old values that happen still to be there. The caller is told how many places count and ignores the rest.

No second list was made. That is the point of the pattern: when the data is large, rearranging it where it stands can matter as much as the time taken.

In the lab

You will decide which move can help, follow the two positions inward, and say which pairs each move discards. You will write the best pair on a budget, which must keep going after it has found a pair, and count the pairs that fit a limit, where one move counts many pairs at once. You will find the values two sorted lists share, and close the gaps in a row of seats without a second list. Then four assignments: a phrase that reads the same both ways, a pair finder with two mistakes, three items for a gift card, and one problem that does not tell you where the two positions come in.