Two Sum
Given an array of integers and a target, return the indices of the two numbers that add up to the target.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
Scan the array once while storing each value's index in a dictionary. For every number, check whether target − number has already been seen.
Pattern: Arrays & hashing. Trade memory for speed: sets and dictionaries answer 'have I seen this?' in O(1).
Complexity
| Measure | Bound |
|---|---|
| Time | O(n) |
| Extra space | O(n) |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.