Two Sum
Problem Description
Given an integer list and a target, return the indices of two distinct elements whose sum equals the target. Assume exactly one pair exists.
Example: nums=[3, 7, 2, 5], target=10 returns (0, 1) because 3 + 7 = 10.
Think about: A value may be used only once, even when the target is twice that value.
Worked solution Open when you’re ready to compare your approach
Approach
For each value, compute the complement target - value. If the complement appeared at an earlier index, return those two indices. Otherwise remember the current index. Looking up before inserting prevents using one element twice.
def two_sum(nums: list[int], target: int) -> tuple[int, int]:
index_by_value = {}
for index, value in enumerate(nums):
complement = target - value
if complement in index_by_value:
return index_by_value[complement], index
index_by_value[value] = index
raise ValueError('No pair found')
The dictionary gives O(n) expected time and O(n) space. The final exception makes the function safe if the input violates its stated assumption.
Check yourself: What happens for [5, 5] with target 10?
Worked trace
With nums=[3, 7, 2, 5] and target=10, start with an empty map. At index 0, the complement of 3 is 7; record 3 → 0. At index 1, the complement of 7 is 3, which is already mapped to 0. Return (0, 1). The map stores the index so the result identifies the original elements, not only their values.
Why it works and what to watch for
Immediately before processing an index, the map contains only earlier elements. Thus a found complement forms a pair with two distinct indices. Checking before insertion is essential when the target equals twice the current value: one occurrence alone is not a valid pair. Duplicate values are fine; with [3, 3] and target 6, the second 3 finds the first. The stated problem guarantees an answer. If that guarantee is removed, change the return type and explicitly return None after the loop. Brute force checks every pair in O(n²) time and uses O(1) extra space; the map trades O(n) space for expected O(n) time.
Step 2 of 7 · Core interview practice
Put this step into practice.
Explain what you store before each iteration and why the lookup is correct.
Enable JavaScript to save progress. You can still continue through the path.
