Two-Sum on a Sorted Array
Given a sorted array of $n$ integers `nums` and a target integer `target`, find all pairs of indices $(i, j)$ with $i < j$ such that `nums[i] + nums[j] == target`.
**Constraints:**
-
\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: `[(0, 3), (1, 2)]` (since
+4 = 5$ -- wait,
+6 = 7$... let me correct: we need pairs summing to 6, so
+4 = 6$ gives $(1, 3)$ and no others). Actually: Output: `[(1, 3)]`. Explanation: `nums[1] + nums[3] = 2 + 4 = 6`.
- Input: `nums = [1, 1, 2, 3, 4, 5]`, `target = 6`. Output: `[(1, 4), (2, 3)]` (or `[(0, 4), (1, 4), (2, 3)]` depending on whether duplicates at distinct indices count). Explanation: +5 = 6$ and
+4 = 6$.
Solve this in $O(n)$ time using the two-pointer technique (assuming the array is already sorted). Compare with the hash map approach for unsorted arrays.Open the full interactive solver, hints, and worked solution →