MiddleCodeVery commonNot answered yet
Two Sum: indices of two numbers summing to a target
Return the indices of the two numbers that add up to target.
Requirements:
- Assume exactly one valid pair; return its two indices.
- Do not use the same element twice.
- Aim for O(n) time, not the O(n²) brute force.
def two_sum(nums, target):
# your code hereWrite the implementation.
Use a dict from value to index: for each n, if target - n is already seen, return both indices; otherwise store n -> i. One pass, O(n) time and O(n) space — versus the O(n²) brute-force double loop. enumerate gives the index cleanly.
- ✗Returning the values rather than their indices
- ✗Using the same element twice for the pair
- ✗Settling for the O(n²) double loop when O(n) is expected
- →How would you adapt this if the list were already sorted?
- →What changes if there can be several valid pairs, or none?
Contents
Task
Implement two_sum: return the indices of the two numbers that add up to target, in one pass.
Solution
def two_sum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
if target - n in seen:
return [seen[target - n], i]
seen[n] = i
return []Key points
- Single pass: the complement
target - nis looked up in O(1) in the dict, so O(n) overall. - Store
nafter the check — otherwise an element could pair with itself. - The double-loop brute force is also correct but O(n²); the dict trades space for speed.
Contents
