Two pointers work when moving one boundary lets you rule out a set of impossible answers. For a sorted array and a target pair sum, the order of the values supplies that rule. Explain what a movement eliminates before presenting the code.

This exercise uses Python 3 as a readable implementation. It requires a nondecreasing input and returns two different indices, not two distinct values. Duplicate values are allowed.

Why can a pointer move safely?

Start with the smallest and largest remaining values. If their sum is too small, keeping the left value and choosing any smaller right value cannot reach the target. The left value can therefore be discarded. If the sum is too large, the same reasoning discards the right value.

def target_pair(values, target):
    left, right = 0, len(values) - 1
    while left < right:
        total = values[left] + values[right]
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return None

assert target_pair([1, 2, 4, 8], 6) == (1, 2)
assert target_pair([3, 3], 6) == (0, 1)
assert target_pair([3], 6) is None
assert target_pair([], 6) is None
assert target_pair([-5, -2, 3, 8], 1) == (1, 2)

The condition left < right prevents using one position twice. The example with two threes is valid because there are two positions. If the task instead asks for unique value pairs, that is a different output contract.

What is the invariant?

At each step, any not-yet-ruled-out pair lies inside the current interval. A movement removes only a boundary that cannot be part of an answer within that interval. The interval shrinks until a match is found or fewer than two positions remain.

Do not merely say “the array is sorted” as a proof. Connect sorted order to the comparison that lets you remove a boundary. That is what makes this strategy more than a lucky sequence of tests.

What if the array is not sorted?

The movement proof no longer holds. You could sort a copy, but then original indices need to be preserved if the caller needs them. Another design uses a lookup of previously seen complements. It has different storage and ordering trade-offs.

Clarify whether changing the input is permitted and whether the output refers to original positions. An implementation that returns indices into a sorted copy can be incorrect even when it finds the right values.

How do you discuss complexity?

Each movement makes the interval smaller. There are at most a linear number of pointer movements, and the code uses constant extra state. This assumes array access and arithmetic have the costs intended by the problem's numeric model.

Sorting would add a separate cost. Do not describe a solution that sorts first as linear overall. State which work is included in your estimate.

Which cases reveal mistakes?

  • Empty and one-element input.
  • A valid pair using equal values at different positions.
  • Negative values and a target between them.
  • No valid pair even though individual values are present.
  • A pair at the two outer boundaries.

For a stronger check, compare small sorted arrays against a simple nested-loop reference implementation. The slower version can be useful as a test oracle even when it is not your final algorithm.

How to present the answer aloud

State the sorted-input requirement, define what the returned pair means, explain one safe movement, then walk a small example. Finish by naming the cost and an edge case. That order makes the reasoning visible before the code becomes the center of the conversation.

References and next practice

ocw.mit.edu — algorithms

Browse interview topics · Practise a question in Interview Challenge · How to Answer Technical Interview Questions Out Loud