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.
Quick Answer: 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)
Solution
from typing import List
from collections import Counter
def two_sum_unique_pairs(nums: List[int], target: int) -> List[List[int]]:
freq = Counter(nums)
result: List[List[int]] = []
for x in sorted(freq.keys()):
y = target - x
if y < x:
continue # ensure a <= b and avoid duplicates
if y not in freq:
continue
if x == y:
if freq[x] >= 2:
result.append([x, y])
else:
result.append([x, y])
return result
Explanation
Build a frequency map of values. Iterate the unique values x in ascending order and compute y = target - x. To avoid duplicate pairs, only consider x when y >= x (ensuring a <= b). If y is present in the map, emit [x, y]; for the special case x == y, ensure there are at least two occurrences. Sorting unique values guarantees the output pairs are lexicographically ordered by (a, b).
Time complexity: O(n log n). Space complexity: O(n).
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.