Two-Sum on a Sorted Array
Given a sorted array of $n$ integers nums and a target integer target, return the index pairs $(i, j)$ with $i < j$ and nums[i] + nums[j] == target as produced by the standard two-pointer scan, in the order the scan finds them.
The canonical scan (this is what makes the answer unique and auto-gradable): start left = 0, right = len(nums) - 1. While left < right, let s = nums[left] + nums[right]: - if s == target: record [left, right], then advance both pointers (left += 1, right -= 1) - if s < target: left += 1 - if s > target: right -= 1
Constraints: - $1 \leq n \leq 10^5$ - $-10^9 \leq$ nums[i] $\leq 10^9$ - The array is sorted in non-decreasing order
Examples:
- Input:
nums = [1, 2, 3, 4, 6],target = 6. Output:[[1, 3]]. Explanation:nums[1] + nums[3] = 2 + 4 = 6; the scan finds no other pair.
- Input:
nums = [1, 1, 2, 3, 4, 5],target = 6. Output:[[0, 5], [2, 4]]. Explanation: the scan records[0, 5]($1+5$), advances both pointers past it, then records[2, 4]($2+4$). Note[1, 5]also sums to 6 but the canonical scan never visits it, because both pointers move after a match. Your output must follow the scan, not list every valid pair.
Solve it in $O(n)$ time with the two-pointer technique (the array is already sorted). Compare with the hash-map approach for unsorted arrays.
Hints
- Since the array is sorted, what can you infer about the sum when you pair the smallest available element with the largest?
- Use two pointers starting at opposite ends of the array. If the sum is too small, advance the left pointer. If too large, retreat the right pointer.
- Each pointer moves at most $n$ times (always forward for left, always backward for right), so total work is $O(n)$ regardless of how many matches exist.
Worked Solution
The array is sorted, so a two-pointer scan finds all pairs in a single O(n) pass. Start left at the smallest element and right at the largest. The sum nums[left] + nums[right] tells you which pointer to move:
- If the sum is too small, only advancing
leftcan increase it. - If the sum is too large, only retreating
rightcan decrease it. - If the sum equals the target, record the pair
[left, right], then move both pointers inward to look for the next distinct pair.
Return the list of [i, j] index pairs in the order they are produced (do not return the values themselves, and do not stop at the first match — collect them all).
```python def two_sum_sorted(nums, target): # nums is sorted in non-decreasing order. Canonical two-pointer scan. result = [] left, right = 0, len(nums) - 1 while left < right: s = nums[left] + nums[right] if s == target: result.append([left, right]) left += 1 right -= 1 elif s < target: left += 1 else: right -= 1 return result ```
Intuition
The two-pointer technique on a sorted array is one of the most fundamental algorithmic patterns. The reason it works is monotonicity: moving the left pointer right can only increase the sum, and moving the right pointer left can only decrease it. This means each comparison eliminates either the current left element or the current right element from further consideration, guaranteeing linear progress.
This pattern generalizes far beyond two-sum. Three-sum reduces to fixing one element and running two-pointer on the rest. Container-with-most-water, trapping-rain-water, and many interval problems use the same inward-converging pointer idea. In quant interviews, the sorting + two-pointer combo comes up in problems about finding pairs of assets with a target correlation, matching trades, or efficiently computing pairwise statistics on ordered data.