Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers that add up to target. Assume exactly one solution; you may not reuse the same element.
Answers use simple, clear English.
Quick interview answer
Scan once with a hash map from value → index. For each nums[i], look up need = target - nums[i]. If found, return [map[need], i]; else store nums[i] → i.
Detailed answer
Scan once with a hash map from value → index. For each nums[i], look up need = target - nums[i]. If found, return [map[need], i]; else store nums[i] → i. This finds the pair in O(n) time. Sorting + two pointers works for values but complicates index recovery. State the unique-answer assumption in interviews.
Full explanation
Sorting + two pointers works for values but complicates index recovery. State the unique-answer assumption in interviews.
Real example & use case
Checkout promo engine: find two line items whose prices sum exactly to a gift-card balance for an auto-apply combo.
Pros & cons
Pros: one-pass O(n), easy to explain. Cons: O(n) memory; streaming with tiny RAM may force sort+two-pointer tradeoffs.
Code example
def two_sum(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
raise ValueError('no pair')Practice code · python (view only · no execution)
def two_sum(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
raise ValueError('no pair')Common mistakes
Reusing the same index; forgetting to store after lookup.
Best practices
Clarify uniqueness and whether values may repeat.
Follow-up questions
- Multiple valid pairs?
- Duplicate values?