Two Sum Algorithm in Python
The Two Sum problem is a common introduction to hash tables and trading extra memory for faster lookup.
What is Two Sum Algorithm?
The Two Sum problem is a common introduction to hash tables and trading extra memory for faster lookup.
Find two list values that add to a target in one pass.
When should you use it?
- Practice problem solving and data structures.
- Process data when every algorithm step must be explicit.
- Prepare for programming exercises, exams, and interviews.
Example code
main.py
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
print(two_sum([2, 7, 11, 15], 9))Expected output
[0, 1]How it works
The dictionary stores values already visited. Looking up the required complement makes the algorithm O(n) time with O(n) extra space.
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.