Two pointers in Python

Problem

The gift card and every pair

A customer has a gift card and wants to spend it to the cent: two products that together cost exactly as much as the card. The site looks for them with two nested loops, checking every pair:

checks = 0


def all_pairs(prices, card):
    global checks
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            checks += 1
            if prices[i] + prices[j] == card:
                return (i, j)
    return None

The price list is 1000 products at €2, €4, …, €2000, and the card is for €2001. The sum of two even prices is never odd, so there is no pair. This is the worst case: the loops go all the way to the end.

n = 1000
prices = [2 * (i + 1) for i in range(n)]
card = 2 * n + 1
pair = all_pairs(prices, card)
print("Pair: " + ("none" if pair is None else "found"))
print(f"Checks: {checks}")

Pair: none
Checks: 499500

Almost half a million checks for 1000 products. There are n(n − 1) / 2 pairs, so this is O(n²): for 100,000 products it becomes about 5 billion.

And the price list is sorted by price, yet the loops make no use of it.

The idea

One on the left, the other on the right

Put one finger on the cheapest price and another on the most expensive. The fingers are indexes: lo and hi. Add the two prices:

if the sum equals the card, you are done;
if it is too little, the cheap price drops out: even with the most expensive price still in play, it is not enough. lo moves one price to the right;
if it is too much, the expensive price drops out: it is too much even with the cheapest one. hi moves one price to the left.

Every step throws away one price for good, and no pair that is the answer gets lost. When lo and hi meet, the prices have run out. At most n − 1 steps: O(n).

This is called two pointers: two indexes that walk along the array, and every comparison says which one of them moves. Here they walk towards each other. You know the idea from binary search, where lo and hi hold the range. There every probe throws away half, here it throws away one price.

The condition is the same: the array has to be sorted. Only then is "to the right is more expensive" true.

See it

lo and hi in the price list

def find_pair(prices, card):
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            lo += 1
        else:
            hi -= 1
    return None

prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
pair = find_pair(prices, 50)
if pair is None:
    print("No pair for €50")
else:
    lo, hi = pair
    print(f"€{prices[lo]} + €{prices[hi]}")

€19 + €31

def find_pair(prices, card):
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            lo += 1
        else:
            hi -= 1
    return None

Step by step, in words

The price list is sorted: 10 prices. The gift card is €50. lo is on the cheapest price, hi on the most expensive.
€3 + €36 = €39 < €50: too little. Even the most expensive price is not enough for €3, so €3 drops out: lo moves right.
€5 + €36 = €41 < €50: too little. Even the most expensive price is not enough for €5, so €5 drops out: lo moves right.
€8 + €36 = €44 < €50: too little. Even the most expensive price is not enough for €8, so €8 drops out: lo moves right.
€12 + €36 = €48 < €50: too little. Even the most expensive price is not enough for €12, so €12 drops out: lo moves right.
€15 + €36 = €51 > €50: too much. €36 is too much even with the cheapest price, so €36 drops out: hi moves left.
€15 + €31 = €46 < €50: too little. Even the most expensive price is not enough for €15, so €15 drops out: lo moves right.
€19 + €31 = €50: exactly the card. findPair returns the indexes 5 and 8.
7 sums instead of 45 pairs. Every step throws away one price for good, so there are at most n − 1 steps.

The function returns a tuple with the two indexes, and None when there is no pair. The sum is in total, not in sum: sum is a built-in function, and it is better not to hide it behind a variable.

More precisely, if you are curious

Why no pair gets lost. Say the answer is the pair of indexes i and j, i < j. While lo ≤ i and hi ≥ j, the pointers cannot jump over the answer:

if lo < i, the sum of lo and hi is at most the sum of i and hi. If it is too little, lo rightly moves right without passing i;
if hi > j, in the same way hi rightly moves left without passing j.

When lo reaches i and hi reaches j, the sum is exactly the card. If there are several pairs, the pointers find the outermost one: the one with the cheapest price.

Try it

Predict which pair

The card is €43. The price list has two pairs with that sum: €12 + €31 and €19 + €24. What does the program print?

def find_pair(prices, card):
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            lo += 1
        else:
            hi -= 1
    return None


prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
pair = find_pair(prices, 43)
if pair is None:
    print("No pair for €43")
else:
    lo, hi = pair
    print(f"€{prices[lo]} + €{prices[hi]}")

Answer

No pair for €43

€19 + €24

€12 + €31

Try it

Fill in

The sum is smaller than the card. Which pointer moves, and which way?

def find_pair(prices, card):
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            
        else:
            hi -= 1
    return None

Try it

Find the bug

The card is €50, and €19 + €31 is in the price list. The function says there is no pair:

prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
pair = find_pair(prices, 50)
if pair is None:
    print("No pair for €50")
else:
    lo, hi = pair
    print(f"€{prices[lo]} + €{prices[hi]}")

No pair for €50

Pick the line with the bug.

See it

How many steps

The same price list of 1000 products and the card for €2001, and the function counts the steps of its loop:

steps = 0


def find_pair(prices, card):
    global steps
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        steps += 1
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            lo += 1
        else:
            hi -= 1
    return None

n = 1000
prices = [2 * (i + 1) for i in range(n)]
card = 2 * n + 1
pair = find_pair(prices, card)
print("Pair: " + ("none" if pair is None else "found"))
print(f"Steps: {steps}")

Pair: none
Steps: 999

999 steps instead of 499,500 checks. The two functions give the same answer, and for 100,000 products the difference is 99,999 steps against about 5 billion.

Run them in the browser. The third curve is for an unsorted price list: first merge sort, then the two pointers.

Every pair O(n²)
Two pointers (sorted list) O(n)
Sort, then two pointers O(n log n)

Algorithm	n = 10	n = 1,000	n = 10,000	n = 100,000
Every pair	45	499,500	49,995,000	≈ 4,999,500,000
Two pointers (sorted list)	9	999	9,999	99,999
Sort, then two pointers	31	9,692	130,424	1,636,539

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

def find_pair(prices, card):
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            lo += 1
        else:
            hi -= 1
    return None

We do not run every pair above 10,000: those values are ≈. Sorting costs more than the pointers themselves, but its curve is O(n log n) and still far below O(n²).

The idea

Is the list sorted

Two pointers need a sorted array. When it is not:

Sort it first. Sorting is O(n log n), the pointers O(n), in total O(n log n). For 100,000 prices that is about 1.6 million operations against about 5 billion. Sorting wins almost every time.
If you search many times in the same list (every customer with a different card), you sort once, and every search after that is O(n).
The indexes change. After sorting, prices[5] is no longer the fifth product of the catalogue. If you need the products, sort pairs (price, product) or objects by price.

prices = [27, 3, 36, 15, 8, 31, 19, 5, 24, 12]
prices.sort()
print(prices)
pair = find_pair(prices, 50)
if pair is None:
    print("No pair for €50")
else:
    lo, hi = pair
    print(f"€{prices[lo]} + €{prices[hi]}")

[3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
€19 + €31

There is also a way without sorting: you go over the prices once and keep the ones you have seen in a set. For each price you ask whether card − price has already been seen. That is O(n) on average, with a hash table and n extra memory. Two pointers use no extra memory, but they need a sorted array.

See it

The same idea: merging and duplicates

The two pointers do not always walk towards each other. Sometimes they walk in the same direction.

Merging two sorted lists. The orders from the website and from the phone are numbered by one counter but kept apart, each list sorted. The daily report wants one sorted list. i walks along the first, j along the second, and each time the smaller number goes into the result. This is the merge from merge sort:

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.extend(a[i:])
    result.extend(b[j:])
    return result

web = [1003, 1007, 1012, 1020]
phone = [1001, 1009, 1010, 1031, 1044]
print(merge(web, phone))

[1001, 1003, 1007, 1009, 1010, 1012, 1020, 1031, 1044]

Duplicates in place. The prices from an import are sorted, but with duplicates, and the filter has to show every price once. read reads every price, and write is the place for the next new one. Everything before write is finished and free of duplicates:

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

prices = [5, 5, 8, 12, 12, 12, 19, 24, 24]
k = unique(prices)
del prices[k:]
print(f"Different prices: {k}")
print(prices)

Different prices: 5
[5, 8, 12, 19, 24]

A list in Python can be shortened in place: del prices[k:] removes everything after the first k.

Both are O(n): each pointer goes over the list once.

See it

A mirror promo code

The "Mirror code" campaign accepts only promo codes that read the same from both ends. The pointers start at both ends and compare character by character until they meet:

def is_mirror(code):
    lo = 0
    hi = len(code) - 1
    while lo < hi:
        if code[lo] != code[hi]:
            return False
        lo += 1
        hi -= 1
    return True

print(is_mirror("AB7CC7BA"))
print(is_mirror("AB7CD7BA"))

True
False

More precisely, if you are curious

The same check can be written on one line, by comparing the code with a reversed copy:

code = "AB7CC7BA"
print(code == code[::-1])

True

code[::-1] is a slice with step −1: a new string of the same length.

The answer is the same and it is still O(n). The difference: the copy is n more characters of memory and is always made in full, while the pointers stop at the first difference. For an 8-character promo code it does not matter. For checking millions of lines in a log it does.

The same pointers reverse an array in place: swap lo and hi, move them inwards.

Exercise

Closest to the card

Solve the task in your editor.

Closest to the card. There is not always an exact pair. Then the shop offers the two products that together come closest to the card without going over it. The price list is €3, €5, €8, €12, €15, €19, €24, €27, €31 and €36, and the card is €45. With two pointers: if the sum is within the card, remember it if it is better than the best so far, and move lo. Otherwise move hi.

Closest to €45: €8 + €36 = €44

More tasks

A mirror code with dashes. The promo codes are printed with dashes: AB7-CC-7BA. Skip the dashes: each pointer jumps over them before comparing.
Two per trip. The parcels are sorted by weight, and one courier trip carries at most two parcels of up to 30 kg in total. How many trips are needed at the least? Put the lightest with the heaviest if they fit, otherwise the heaviest goes alone.
Common products. Two sorted lists of product numbers: from the warehouse and from the order. Find which numbers are in both, with two pointers in the same direction.

Test

Check yourself

1. The price list is sorted. lo is on €8, hi on €36, the card is €50. The sum is €44. What do you do?hi moves leftYou go back to the startlo moves right: €8 is not enough even with the most expensive price

2. The price list has 100,000 products, and there is no pair for the card. How many sums do the two pointers compute?About 5 billionAbout 17, as many as binary search99,999

3. The price list is not sorted. Which of the three is fastest?Every pair (O(n²)), because sorting costs too muchSort it (O(n log n)) and run the two pointers (O(n))Run the two pointers straight on the unsorted list

4. You remove the duplicates from the sorted list in place, with read and write. Which is true?read and write walk towards each other from both endsread goes over every element, and write shows where the finished part endsYou need a new list of the same length

5. Why is checking a mirror promo code with two pointers better than comparing it with a reversed copy?It is O(log n)The reversed copy gives a wrong answerIt makes no copy and stops at the first difference

Two pointers

Cookies