Given an array of integers and a target, return the indices of the two numbers that add up to the target. Each input has exactly one solution, and you may not use the same element twice.
Before you code
The brute-force answer tries every pair: O(n²). The hash map answer walks the array once. For each number x, the partner you need is target - x; if you have already seen it, you are done.
Hints
- Store each number you pass in a map from value to index.
- Check for the partner before storing the current number, so a number can't pair with itself.
- Duplicates such as
[3, 3]with target 6 still work: the first 3 is stored, and the second finds it.
Production & complexity notes
When solving Two sum on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Turning a key into a slot to reinforce the underlying pattern.
What it practices
Turning a value straight into a slot so that "have I seen the partner?" takes one lookup, from Turning a key into a slot.