Two Sum
Given an array nums and a target, return the indices of the two numbers that add up to target. Exactly one valid answer exists, and you may not reuse the same element twice.
Intuition
We are hunting for a pair that sums to the target. The brute-force instinct is to try every pair, but that repeats a lot of work. The key realization: for any number, its needed partner is fixed — it is target − num. So instead of searching for partners, remember every number already seen and, for each new number, ask “have I already met your partner?”
Approach
Start with brute force — and notice what's wasteful
The most direct idea is: try every pair. For each index i, loop over every later index j and check if nums[i] + nums[j] == target. This is correct and easy to reason about, but it does a lot of repeated work — for each element you re-scan the entire rest of the array, giving O(n²) time. The key observation is that the inner loop is really just asking one question over and over: “is the specific number I need sitting somewhere in the array?” Asking that question by scanning is the slow part.
Turn the search into a lookup
For any number num, the partner that completes the pair is fixed — it must be exactly target − num. So instead of searching for that partner each time, we can remember the numbers we've already walked past in a hash map keyed by value. A hash map answers “have I seen this value, and at what index?” in O(1) on average. That single change replaces the entire inner loop: we no longer look ahead, we look back at what we've recorded.
Walk once, checking before storing
Scan left to right. For the current num, compute need = target − num and ask the map whether need is already there. If it is, we've found the two indices and return immediately. If not, we store num → i and move on. The ordering matters: we check before inserting the current number, which is what lets a value pair with an earlier copy of itself (like the two 3s in [3,3]) without a number ever pairing with itself. One pass, O(n) time.
Solution & live demo
Edge cases
We check the map BEFORE inserting the current number, so the first 3 is stored and the second 3 finds it — distinct indices, no reuse.
target − num is plain arithmetic; sign and zero make no difference to the hash lookup.
Overwriting an earlier identical value's index is harmless: any one valid pairing is acceptable and the answer is guaranteed unique.