Skip to content
Work Free practice Coding course Blog Method Results Why me About Enquire Book a call

Coding · Two pointers

Understanding the problem

Lesson · 6 min read · Two pointers

A problem that looks harmless

You are handed a sorted list of prices and asked, repeatedly, whether two of them add up to a given budget. It sounds like a lookup. The first solution almost everyone writes is to try every pair:

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

That is correct, and on the ten-element example in the question it returns instantly. The interviewer then says the array holds a hundred thousand prices and the service answers a thousand queries a second, and the solution falls apart.

How slow is "every pair"?

There are n(n−1)/2 pairs. The table is worth holding in your head, because it is the reason interviewers keep asking this question.

Array sizePairs to checkAt 10⁸ operations a second
1004,950instant
10,000≈ 50 millionabout half a second
100,000≈ 5 billionabout a minute
1,000,000≈ 500 billionabout an hour and a half

Each time the input grows tenfold, the work grows a hundredfold. No faster machine fixes that; the shape of the algorithm has to change.

The information you were given for free

Look again at the input: the array is sorted. The brute force never uses that. It compares 2 with 15 as eagerly as it compares 7 with 11, even though the ordering already tells you a great deal about which pairs are worth looking at.

That is the real lesson, and it generalises far beyond this question: when a question hands you a property you are not using, that property is usually the solution. Sorted input, a fixed alphabet, values bounded by 100, "each element appears at most twice" — every one of those is a hint, not decoration.

Here is what using the ordering buys you. Each step throws away a value for good, so the scan visits each index at most once.

  1. Step 1 / 4
    nums
    10lo31425374115hi
    sum12target10

    Start at the two ends: 1 + 11 = 12, larger than the target of 10.

  2. Step 2 / 4
    nums
    10lo31425374115hi
    sum12target10

    11 is the largest value left. Paired with the smallest value it is already too big, so 11 cannot be in any valid pair at all. Discard it.

  3. Step 3 / 4
    nums
    10lo31425374hi115
    sum8target10

    Now 1 + 7 = 8, too small. By the same argument in reverse, 1 is too small to pair with anything that remains. Discard it.

  4. Step 4 / 4
    nums
    1031lo425374hi115
    sum10target10

    3 + 7 = 10. Found, after four comparisons rather than fifteen.

What changed

The brute force asks "is this pair the answer?" — a question about one pair, repeated n²/2 times. The scan above asks "can this value be in any answer?" — a question about one value, repeated n times. That shift, from testing candidates to eliminating them, is what the two-pointer pattern is.

If you can argue that one comparison rules a value out for ever, you can usually walk the array once instead of squaring it.