605. The Pair That Adds to the Target
An array is given in NON-DECREASING order, together with a target. Exactly one pair of
positions i < j has a[i] + a[j] = target.
Print those two positions, counting from 1, smaller first.
2 7 11 15, target 9 -> 1 2
1 2, target 3 -> 1 2
## The nested loop, and what sorting buys
Trying every pair is O(n^2). A hash table brings it to O(n) and is the right answer when
the input is unsorted, which is problem 300.
Sorted input allows something better still: O(n) time and O(1) extra memory, with no
table at all.
## The sweep
Start with i at the front and j at the back:
while i < j:
s = a[i] + a[j]
if s == target: answer found
if s < target: i += 1
else: j -= 1
## Why discarding an end is safe
This is the argument to understand, because every problem in this topic repeats its shape.
Suppose a[i] + a[j] < target. Then a[i] paired with ANY remaining partner is too small:
the partners still available are a[i+1] .. a[j], and a[j] is the largest of them, so every
other pairing of a[i] gives an even smaller sum. So a[i] can be in no remaining answer, and
moving i forward discards nothing.
The case s > target is the mirror image: a[j] is too large for every partner that is left.
Without that argument the sweep is a guess. With it, the sweep is a proof.
## Termination
Each step moves exactly one pointer inward, so the gap shrinks by one every time and the loop
runs at most n steps. That is where the linear time comes from.
## On the guarantee
The statement promises exactly one pair, so the sweep always finds it and no "not found" case exists. That is what allows the answer to be a pair of positions with no tie-break rule.
## Boundaries
Two elements are the smallest input and the answer is 1 2.
Values reach 10^9, so a sum reaches 2 * 10^9. Check that against the limit rather than
assuming: a signed 32 bit integer runs from -2147483648 to 2147483647, so
2000000000 and -2000000000 both FIT, with about seven percent to spare. This problem
has no overflow, and 64 bit accumulation here is margin rather than correctness. Use
64 bits for the sum even though the values themselves fit.
## Cost
Time O(n). Space O(1).
Constraints - `2 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - the array is non-decreasing - exactly one pair sums to the target
Input
The first line contains two integers n and target.
The second line contains n integers in non-decreasing order.
Output
Print two integers, the 1-based positions of the pair, smaller first.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.