Two-Sum on a Sorted Array
# Two Sum (Sorted Array) — All Pairs
nums is an array of integers sorted in non-decreasing order. Find every index pair (i, j) with i < j such that nums[i] + nums[j] == target, using the canonical two-pointer scan:
left = 0,right = len(nums) - 1- while
left < right: s = nums[left] + nums[right]- if
s == target: record[left, right], thenleft += 1andright -= 1 - elif
s < target:left += 1 - else:
right -= 1
Because the two pointers each move at most once past every element, the scan finds one pair per matching (left, right) collision. Duplicate values yield distinct index pairs.
## Function signature
```python def two_sum_sorted(nums, target): ... ```
Return the list of recorded pairs as [i, j] lists, in the order produced by the scan.
Example
two_sum_sorted([1, 1, 2, 3, 4, 5], 6) -> [[0, 5], [2, 4]]
The pointers first collide at indices 0 and 5 (1 + 5 == 6), then move inward and collide at indices 2 and 4 (2 + 4 == 6); the pointers cross before any further match, so those two pairs are the full result.
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.