Two Sum
Given an array of numbers nums and a target, return the indices of the two numbers that add up to the target. Assume exactly one solution exists, and don't use the same element twice.
twoSum([2, 7, 11, 15], 9) → [0, 1]
Start with brute force, then get it to O(n).
🧪 Practice
Implement twoSum(nums, target) in O(n) time.
Output appears here. Press Run or Ctrl/⌘ + Enter.
Reveal model answer & explanation
Model answer
Brute force: check every pair with two loops, which is O(n²) time and O(1) space. Say this first, then improve it.
Optimal: one pass with a hash map. For each nums[i], compute need = target - nums[i]. If need is already in the map, you've found the pair. Otherwise store nums[i] → i.
- Time: O(n), since each lookup is O(1) on average
- Space: O(n) for the map
Why insert after checking? It prevents using the same element twice (for example [3] with target 6).
Follow-ups you might get: what if the array is sorted? (Two pointers, O(1) space.) What if there are multiple pairs? (Collect them instead of returning.)