Find all pairs summing to target in sorted array
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: This question evaluates skills in array manipulation, handling duplicates, and algorithmic efficiency with attention to time and space complexity analysis.
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
Examples
Input: ([1, 2, 3, 4, 5], 6)
Expected Output: [[0, 4], [1, 3]]
Explanation: 1+5=6 -> [0,4]; 2+4=6 -> [1,3]; 3 alone (middle) cannot pair with itself.
Input: ([1, 1, 2, 2, 3, 3], 4)
Expected Output: [[0, 5], [2, 3]]
Explanation: Value pair (1,3) recorded once as [0,5]; value pair (2,2) recorded once as [2,3].
Hints
- Because the array is sorted, you can place one pointer at the start and one at the end and move them toward each other.
- If the current sum is too small, advance the left pointer; if too large, retreat the right pointer; if equal, record the pair.
- After recording a match, skip past all equal values on both sides so the same value combination is not recorded twice.