← Python roadmap

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.

  1. Scan once.
  2. Check target-x among earlier values.
  3. 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?