Eliminate candidates with two pointers
Use the two ends of a sorted array to find a pair without checking every combination.
Understand the idea
Start with a sorted array, left = 0, and right = n − 1. If the sum is too small, every partner for the current left value is also too small; discard that left position. If the sum is too large, every partner for the current right value is too large; discard that right position.
Trace a small example
For [1, 3, 4, 7, 10] and target 11, the first sum is 1 + 10 = 11. For target 9, discard 10, then discard 1, then discard 7, then discard 3: no pair remains. The invariant is that every not-yet-excluded answer uses positions inside the current interval.
Conditions and cost
Use left < right to require two distinct positions. Sorting costs O(n log n); the scan costs O(n). Preserve original indices before sorting when the output asks for them. A wide sum must be computed in a wide type.
Prefix sum explorer
Query [l, r] is zero-based and inclusive. P[k] stores the total of the first k values; P[0] is zero.
Input array a
Prefix array P
Preprocess once in O(n). Each range sum then takes O(1).
Guided simulation · Change the inputs to test your understanding.
In a sorted array, why can left advance when a[left] + a[right] is too small?
Turn the idea into code
Find a distinct-position pair summing to 10 in [2, 3, 5, 7, 9], or show that none exists.
Give me a hint
Write down each endpoint sum and justify the pointer you move.
Show the explained solution
2 + 9 is too large, so remove 9. 2 + 7 is too small, so remove 2. 3 + 7 = 10; the pair is at zero-based positions 1 and 3.
Your notes
Mark complete when you can explain it yourself.