Identify Number Pairs Adding to Target in Array
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Scenario
Coding round to identify all number pairs that add up to a target in an array containing duplicates.
##### Question
Given an integer array (may contain duplicates) and a target sum, return all pairs of values whose sum equals the target, e.g. [1,2,1,0], target=3 -> [(1,
2)].
##### Hints
Use hashmap or sort+two-pointer; account for duplicate counts.
Overview: This question evaluates skills in array processing, pair-sum detection, handling duplicate values and multiset counts, and reasoning about algorithmic complexity and correctness.
Given an integer array nums (may contain duplicates) and an integer target, return all unique value pairs [a, b] such that a + b == target. Each pair must appear once regardless of how many times the values occur. Include [x, x] only if nums contains at least two occurrences of x. Return pairs sorted: within each pair a <= b, and the list sorted lexicographically by (a, b). Indices do not matter.
Constraints
- 0 <= n <= 200000
- -10^9 <= nums[i], target <= 10^9
- Return value-based pairs only; indices are irrelevant
- Include [x, x] only if count(x) >= 2
- Within each pair a <= b; output list sorted lexicographically by (a, b)
Hints
- Count frequencies with a hashmap; iterate unique values x and check if target - x exists.
- To avoid duplicates, only form pairs where x <= target - x.
- If x == target - x, include [x, x] only when frequency[x] >= 2. Alternatively, sort the array and use two pointers while skipping duplicates.