Find all pairs summing to target in sorted array

Given a non-decreasing array of integers nums and an integer target, return all unique pairs of indices (i, j) with i < j such that nums[i] + nums[j] == target. Use 0-based indices and list pairs in increasing order of i, then j. Each value may be used at most once per pair; if duplicates create the same value pair, include that pair only once. Aim for an O(n) two-pointer solution and analyze complexity.

Find all pairs summing to target in sorted array

Given a non-decreasing array of integers nums and an integer target, return all unique pairs of indices (i, j) with i < j such that nums[i] + nums[j] == target.

Use 0-based indices and list pairs in increasing order of i, then j. Each value may be used at most once per pair; if duplicate values would create the same value pair, include that pair only once (return the first qualifying index pair for that value combination).

Aim for an O(n) two-pointer solution and analyze the complexity.

Example:

• nums = [1, 1, 2, 2, 3, 3], target = 4 -> [[0, 5], [2, 3]] (value pairs (1,3) and (2,2), each counted once)
• nums = [1, 2, 3, 4, 5], target = 6 -> [[0, 4], [1, 3]]

Constraints

• 0 <= len(nums) <= 10^5
• nums is sorted in non-decreasing order
• -10^9 <= nums[i], target <= 10^9
• Return index pairs [i, j] with i < j
• Each distinct value-pair must appear at most once

Hints

1. Because the array is sorted, you can place one pointer at the start and one at the end and move them toward each other.
2. If the current sum is too small, advance the left pointer; if too large, retreat the right pointer; if equal, record the pair.
3. After recording a match, skip past all equal values on both sides so the same value combination is not recorded twice.