Pair Sum - Unsorted
Given an unsorted array of integers nums and an integer target,
return the indices of the two numbers that add up to target.
You may assume that each input has exactly one valid answer, and you may not use the same element twice. Return the indices in any order.
Example 1
Input: nums = [3, 7, 1, 9], target = 8
Output: [0, 2]
Explanation: nums[0] + nums[2] = 3 + 1 = 8
Example 2
Input: nums = [4, 4, 2], target = 8
Output: [0, 1]
Explanation: nums[0] + nums[1] = 4 + 4 = 8
Constraints
2 <= nums.length <= 10^5-10^9 <= nums[i], target <= 10^9- Exactly one valid pair of indices exists.
A brute-force check of every pair costs O(n^2). We can do better by
noticing that for each value x, the only thing we need to know is
whether target - x (its "complement") has already appeared earlier
in the array — and if so, at which index.
Walk the array once, keeping a hash map from value seen so far to its index. At each element, first check whether its complement is already in the map (an O(1) lookup); if so, we've found our pair. Otherwise, record the current value and index in the map and continue. Because we check before inserting, we never match an element with itself.
def pair_sum_unsorted(nums: list[int], target: int) -> list[int]:
seen_index: dict[int, int] = {}
for i, x in enumerate(nums):
complement = target - x
if complement in seen_index:
return [seen_index[complement], i]
seen_index[x] = i
return [] # problem guarantees a solution exists
Complexity: O(n) time, since we make a single pass with O(1) average-case map operations. O(n) space for the hash map in the worst case.
Share this question