Two-Sum on a Sorted Array

Worked Solution

How to Think About It

Heuristic: *sorted array plus a pair condition means two pointers converging from the ends*. The sum nums[left] + nums[right] is monotone in each pointer, so one comparison tells you which pointer can never be part of a new match. The one extra idea is runs of equal values: a match is a match between two *values*, and every copy of the left value pairs with every copy of the right value.

Quick Estimate

Take nums = [1, 1, 2, 2], target = 3. The value 1 occupies indices 0 and 1 (run length 2); the value 2 occupies indices 2 and 3 (run length 2). Every copy of 1 pairs with every copy of 2, so there are $2 \times 2 = 4$ pairs: [0, 2], [0, 3], [1, 2], [1, 3]. A scan that records [left, right] and then moves both pointers by one finds only [0, 3] and [1, 2], so it misses half the answer. In general, a match between a left run of length $a$ and a right run of length $b$ contributes $a \cdot b$ pairs, and a single run of length $m$ whose value $v$ has $2v = $ target contributes $\binom{m}{2}$ pairs (for [3, 3, 3, 3, 3], target = 6, that is $\binom{5}{2} = 10$).

Approach

Start left = 0, right = n - 1. While left < right, compare s = nums[left] + nums[right] with target:

• If s < target, only advancing left can increase the sum, so left += 1.
• If s > target, only retreating right can decrease the sum, so right -= 1.
• If s == target and nums[left] != nums[right], extend left to the end of its run of equal values and right to the start of its run. Record every [i, j] with i in the left run and j in the right run, then jump both pointers past their runs.
• If s == target and nums[left] == nums[right], every element from left to right equals $v$ with $2v = $ target. Record every pair i < j inside that range and stop.

Formal Solution

*Correctness.* If s < target, then nums[left] + nums[k] <= s < target for every k <= right, so index left has no remaining partner and can be discarded. Symmetrically, if s > target, index right has no remaining partner. On a match with different values $u < w$, any index holding $u$ can only pair with an index holding $w$ (the unique partner value), and both full runs lie inside [left, right] because earlier discards never removed an index with a partner. So the block of run-by-run pairs is exactly the set of pairs that use these two values, and both runs can then be discarded. When nums[left] == nums[right], the whole remaining window is one run of value $v = $ target $/2$, and all of its internal pairs are valid.

*Order.* Matched left values increase over the scan, so the blocks come out with increasing i; inside a block, i ascends in the outer loop and j ascends in the inner loop. The equal-value run sits between all earlier left and right runs, so its pairs come last. The output is therefore already in lexicographic order with no sort needed.

```python def two_sum_sorted(nums, target): # nums is sorted in non-decreasing order; duplicates allowed. result = [] left, right = 0, len(nums) - 1 while left < right: s = nums[left] + nums[right] if s < target: left += 1 elif s > target: right -= 1 elif nums[left] == nums[right]: # One run of equal values v with 2v == target: every pair inside it. for i in range(left, right + 1): for j in range(i + 1, right + 1): result.append([i, j]) break else: # Find the full run of the left value and of the right value. l_end = left while nums[l_end + 1] == nums[left]: l_end += 1 r_start = right while nums[r_start - 1] == nums[right]: r_start -= 1 for i in range(left, l_end + 1): for j in range(r_start, right + 1): result.append([i, j]) left, right = l_end + 1, r_start - 1 return result ```

*Complexity.* The pointer moves (including the run extensions) total at most $n$, and every inner-loop step writes one output pair, so the time is $\boxed{O(n + K)}$ with $K$ the number of pairs returned, and extra space is $O(1)$ beyond the output. $K$ can be as large as $\binom{n}{2}$ when every value equals target $/2$, and no algorithm can beat the size of its output.

*Hash-map comparison.* For an unsorted array, map each value to its list of indices, and for each i look up the indices j > i holding target - nums[i]. That is also $O(n + K)$ expected time but needs $O(n)$ extra memory; the sorted two-pointer version needs none.

Answer

Two pointers from both ends: move left up when the sum is too small and right down when it is too large. On a match, pair the entire run of the left value with the entire run of the right value (or, if the two values are equal, every pair inside that run). This returns all index pairs in lexicographic order in $O(n + K)$ time. Examples: [[1, 3]], [[0, 5], [1, 5], [2, 4]], and [[0, 2], [0, 3], [1, 2], [1, 3]].