Algorithms and data structures · Intermediate

Find a target pair from two endpoints

Use sorted order to justify eliminating pairs, then distinguish duplicates, original indices and the single-item boundary.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Narrow the candidates from both ends
  2. Justify each discarded endpoint
  3. Read the contract before the loop
  4. Decide what duplicates mean
  5. Use an unsorted counterexample
  6. Count monotone pointer movement
  7. Extend to three values without hiding the outer cost
  8. Exercise: explain an endpoint trace
  9. Ask Logeia about this articleCheck your understanding

Narrow the candidates from both ends

Find two different positions whose values sum to a target in a sorted array. For minus two, zero, one, three and five, use target four. The outer pair sums to three, so advance the left end. Zero plus five is too large, so move the right end back. Zero plus three is too small; one plus three finally succeeds. Two equal values are allowed when they occupy different positions. Reusing one position is not allowed.

Two pointer variables alone do not justify the algorithm. The important part is proving that every discarded row or column of candidate pairs cannot contain an answer. State whether sorting is supplied by the caller or performed first. That choice changes the total cost, even though the scan itself is the same.

Justify each discarded endpoint

Suppose the current outer sum is below the target. The right endpoint is the largest remaining value. Pairing the current left value with any smaller remaining partner cannot reach the target either. Every pair involving that left endpoint can therefore be discarded together. Moving the right endpoint inward would only decrease the sum. This is an ordering argument, not a heuristic based on how far the current sum is from the target.

If the outer sum is above the target, the left endpoint is the smallest remaining partner, so every remaining pair using the right endpoint is too large. Discard that endpoint instead. Negative numbers do not invalidate this reasoning when the array remains sorted. This differs from a sum window whose shrinking rule relies on nonnegative elements.

Current sumCandidates eliminatedAction
Below targetPairs using current left endpointIncrement left
Above targetPairs using current right endpointDecrement right
Equal to targetValid distinct positions foundReturn the pair

Read the contract before the loop

The function accepts sorted input and returns an index pair or None. It only examines positions while left is strictly below right, so a single item cannot pair with itself and an empty array never enters the loop. Python integers avoid fixed-width overflow; a port must consider whether adding two values can overflow before comparing with the target. The function deliberately does not spend a separate scan validating sortedness, so that requirement belongs in its documented contract.

The included tests enumerate sorted multisets of lengths zero through six and compare against all distinct index pairs. A returned pair must also have different indices and the required sum. The reference is intentionally simple and independent of the endpoint-elimination rule. Small exhaustive tests provide evidence, while the invariant explains all valid inputs.

python
from itertools import combinations_with_replacement
def pair(a,target):
    left=0;right=len(a)-1
    while left<right:
        total=a[left]+a[right]
        if total==target:return (left,right)
        if total<target:left+=1
        else:right-=1
    return None
for n in range(7):
    for a in combinations_with_replacement(range(-2,3),n):
        for target in range(-5,6):
            result=pair(a,target)
            exists=any(a[i]+a[j]==target for i in range(n) for j in range(i+1,n))
            assert (result is not None)==exists
            if result:assert result[0]<result[1] and a[result[0]]+a[result[1]]==target
assert pair([3],6) is None and pair([3,3],6)==(0,1)
print('sorted multisets lengths0..6 matched brute force')

Decide what duplicates mean

Two copies of three can form target six at distinct positions; one copy cannot. Returning one pair, enumerating every index pair and counting distinct value pairs are different problems. Four copies of three give one value pair but six index pairs. The current function stops at the first match and is not a counting routine.

For complete enumeration or counting, reason about runs of equal values at both endpoints. A quadratic number of required output pairs also imposes a quadratic output cost, even when endpoint movement is linear. Separate the cost of finding groups from the cost of emitting results. Defining the output precisely prevents a seemingly harmless duplicate-skipping rule from silently changing the question being answered.

Use an unsorted counterexample

Run the rule directly on one, four, two with target five. One plus two is too small, so discard the left position. Four plus two is too large, so move the right position back and stop. Yet one plus four was a valid pair. The failed premise was that the right endpoint represented the largest remaining partner. Explain that broken elimination argument rather than merely saying that an unsorted test fails.

Sorting first may be appropriate, but preserving original indices requires carrying them alongside values. A hash-based search provides another tradeoff involving additional storage and expected lookup cost. Compare mutation permission, memory, index requirements and repeated queries. The useful algorithm is the one whose input contract actually holds for the application.

Count monotone pointer movement

Each unsuccessful iteration advances the left pointer or retreats the right one. Neither reverses direction, so at most n minus one iterations are needed for sorted input. Under a fixed-word model the scan costs O(n) time and O(1) additional space. Arbitrarily large Python integers add their own arithmetic cost; the usual statement assumes values fit the chosen computational word model.

If the input must first be sorted, include that cost in the complete operation. For many target queries, separate one-time preparation from repeated scans. Timing comparisons should treat input construction and sorting consistently on both sides. Otherwise a benchmark can reward a prepared input rather than demonstrate the cost of solving the same original task.

Extend to three values without hiding the outer cost

A three-position sum can fix one index and run the endpoint search only to its right. Excluding the fixed position prevents reuse. Trying n fixed positions and doing a linear remaining scan gives the usual quadratic basic method, even though the inner pointers still move only one way. Do not describe the complete problem as linear by counting only its inner loop.

Returning unique value triples also needs duplicate rules for both the fixed value and the endpoints. Enumerating all index triples is another output contract. Identify which proof transfers from the two-value scan and which costs or semantics are newly introduced by the outer iteration. Reusing an algorithmic component is useful, but does not transfer its whole complexity or result guarantee unchanged to the larger task.

Exercise: explain an endpoint trace

For minus three, minus one, two, four, six and target five, record the first three comparisons. The correct answer only contains two: minus three plus six is three, so advance left; minus one plus six equals five, so return indices one and four. There is no third iteration after success. The discarded left value could not reach five with any remaining partner.

Now change the target to twelve. Six appears only once, so pairing it with itself is forbidden and no solution exists. The strict endpoint inequality captures that distinction. For every variation, revisit the input contract, candidate invariant and stopping rule. These explanations matter more than memorizing which pointer moved in one successful example.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path