Two pointers: stop testing pairs and start ruling values out

You're given a sorted list of prices and asked whether any two add up to a budget.

for i in range(n):
    for j in range(i + 1, n):
        if a[i] + a[j] == target:
            return (i, j)

Correct, and instant on the ten-element example. Then the interviewer mentions that the list has 100,000 prices and the service answers a thousand of these queries a second.

How bad "every pair" gets

There are n(n−1)/2 pairs.

Array size	Pairs	At 10⁸ a second
100	4,950	instant
10,000	about 50 million	about half a second
100,000	about 5 billion	about a minute
1,000,000	about 500 billion	about an hour and a half

Ten times the input, a hundred times the work. A faster machine won't save you.

The hint in the question

The list is sorted, and the brute force never uses it. It checks 2 + 15 as carefully as 7 + 11, although the order already tells you which pairs are worth looking at.

When a question gives you a property and your solution ignores it, that property is usually the solution. Sorted input, a small alphabet, values under 100, "each element appears at most twice": those are usually hints.

One pass

Put a pointer at each end:

def pair_sum(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return (lo, hi)
        if s > target:
            hi -= 1      # a[hi] is too big for every partner left
        else:
            lo += 1      # a[lo] is too small for every partner left
    return None

On [1, 3, 4, 5, 7, 11] with a target of 10:

Left	Right	Sum	Conclusion
1	11	12	11 with the smallest value is already too big, so 11 is in no pair. Drop it
1	7	8	1 with the largest value left is too small, so 1 is in no pair. Drop it
3	7	10	found

Three sums instead of fifteen pairs.

The brute force keeps asking "is this pair the answer?". The scan asks something better: can this value be in any answer at all? If one comparison can rule a value out for good, try a single pass before anything cleverer.

If you'd rather watch the pointers move, the original has a stepper: https://geodesicpartners.co.uk/coding-two-pointers-why