Syllabus Lesson 55 of 141 · Speed without the cache
Speed without the cache

Two pointers, no table

Why it matters "Find two things that add up to X" has a famous answer: put everything in a set and look up the partner. It is fast, and it needs a copy of all the data. When the data is sorted, you need almost no memory at all.

A gift service sells bundles of two different products for a fixed bundle price. The product price list is sorted, has no repeats, and sits on an embedded device with very little free memory. For a bundle price, you need the number of product pairs whose prices add up to exactly that price.

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
Your turn

Write count_pairs(tape, target). tape is a Tape of whole-number prices, sorted ascending, with no repeats. Return how many pairs of two different items add up to exactly target (each pair counted once). Budgets: for 20,000 items read at most 60,000 values, and use at most 16,000 bytes of working memory while your function runs (measured with tracemalloc; a set or list of the 20,000 prices is over 150,000 bytes). len(tape) is free.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus