3.45 Two Sum V

3.45.1 Problem Metadata

3.45.2 Description

Given a sorted integer array nums and an integer target, find all unique pairs [a, b] such that a + b = target. Each pair should list the smaller element first, and duplicate pairs must be removed.

3.45.3 Examples

Input: nums = [-2,-1,-1,0,1,2], target = 0
Output: [[-2,2],[-1,1]]

3.45.4 Constraints

  • 2 <= nums.length <= 10^5
  • -10^9 <= nums[i], target <= 10^9
  • nums is sorted in non-decreasing order

3.45.5 Solution - Two Pointers

3.45.5.1 Walkthrough

Place left at the start and right at the end of the array. Compare nums[left] + nums[right] with target and move pointers inward. Whenever a valid pair is found, add it to the result and skip over duplicates on both sides to avoid repeated pairs.

3.45.5.2 Analysis

  • Time Complexity: O(n) - Each element visited at most once by each pointer
  • Space Complexity: O(1) auxiliary space (output list not counted)

Why Two Pointers Works: The sorted array guarantees that skipping duplicates correctly finds all unique pairs. After finding a match at [left, right], we advance both pointers past all duplicate values to avoid counting the same pair multiple times.

Uniqueness Detail: Because the array may contain repeats, the duplicate-skipping logic is essential:

while (left < right && nums[left] == currentLeft) left++;
while (left < right && nums[right] == currentRight) right--;

Why Not Hash Table? For finding all unique pairs in sorted arrays, two pointers is more efficient. Hash table would require additional logic to deduplicate pairs and wouldn’t leverage the sorted property.

When to Use: Standard approach for “find all pairs” problems with sorted input.

3.45.5.3 Implementation Steps

  1. Initialize left = 0, right = nums.length - 1, and an empty result list.
  2. While left < right:
    1. Compute sum = nums[left] + nums[right].
    2. If sum == target, record the pair and move both pointers past duplicate values.
    3. If sum < target, increment left.
    4. Otherwise, decrement right.
  3. Return the collected list of pairs.

3.45.5.4 Code - Java

public List<List<Integer>> twoSumPairs(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        int sum = nums[left] + nums[right];

        if (sum == target) {
            result.add(Arrays.asList(nums[left], nums[right]));

            int currentLeft = nums[left];
            int currentRight = nums[right];
            while (left < right && nums[left] == currentLeft) {
                left++;
            }
            while (left < right && nums[right] == currentRight) {
                right--;
            }
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return result;
}