Return indices of a pair with a target sum
BasicEntry level · 0–1 yearsHashing
Python 3.10+; standard library only. GIL discussion refers to conventional CPython builds, not optional free-threaded builds.
Problem statement
Return the first pair found in left-to-right scanning whose values sum to target, or an empty list.
Match two invoice adjustments without reusing a row.
Input: Integer list nums and integer target.
Output: Two distinct indices or [].
- 0 <= n <= 100000.
- Inputs may contain duplicates and negative values.
- The earliest prior occurrence is retained for each value.
Sample 1
Input: [2,7,11,15], 9 Output: [0,1]
2+7=9.
Sample 2
Input: [3,3], 6 Output: [0,1]
Equal values come from distinct indices.
Brute-force solution
Check every pair of distinct indices until a match is found.
O(n²) time, O(1) auxiliary space; a different pair may be returned on ambiguous input.
def two_sum_slow(nums,target):
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i]+nums[j]==target:
return [i,j]
return []Optimized solution
Store prior values in a dictionary; look up the complement before inserting the current value.
- Scan once.
- Check target-x among earlier values.
- Return matching indices or record x.
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
if target-x in seen:
return [seen[target-x],i]
seen.setdefault(x,i)
return []
print(two_sum([2,7,11,15],9))
Complexity analysis
Time: O(n) expected; dictionary collision costs are implementation-dependent.
Auxiliary space: O(n)
Test cases
- No pair.
- Empty input.
- Duplicate values.
assert two_sum([2,7,11,15],9)==[0,1]
assert two_sum([3,3],6)==[0,1]
assert two_sum([],0)==[]
assert two_sum([1],2)==[]Common mistakes
- Inserting before lookup and reusing an index.
- Ignoring duplicate values.
Key takeaways
- Check before inserting.
- Separate values from indices.
- Clarify pair-selection order.
Follow-up challenges
- How would sorted two pointers differ?
- How would you return all pairs?