Two Sum (Sorted)
Medium · rating 1250 · Two Pointers, Arrays
The first line contains n. The second line has n integers in non-decreasing order. The third line contains a target t. Exactly one pair of positions sums to t — print their 1-based indices i j with i < j.
Constraints: 2 ≤ n ≤ 105
Editorial
Approach
Because the array is sorted, two pointers beat a hash map. Start one pointer at each end. If the pair sums to more than the target, the largest element is too big — move the right pointer in; if it sums to less, move the left pointer out. When the sum matches, you've found the pair.
Why it can't miss
Every step discards exactly the values that can no longer be part of a valid pair, so the two pointers sweep toward each other and examine each element at most once.
i, j = 0, n - 1
while i < j:
s = a[i] + a[j]
if s == t: return (i + 1, j + 1)
if s < t: i += 1
else: j -= 1Complexity
Time: O(n). Space: O(1).
Related problems
- Count Distinct (Sorted) — Medium
- Move Zeroes — Easy
- Heaviest Row — Medium
- Kth Largest Element — Medium
- Most Common Value — Medium
- Transpose a Grid — Medium