Two Sum

Find two indices whose values add up to target. Instead of checking every pair, walk the array once and remember each value's index in a hash map; for each number you only need to ask whether its complement target - x has already appeared.

Traced input: nums = [2, 7, 11, 15], target = 9 → [0, 1]. Original problem: neetcode.io/problems/two-integer-sum

Complexity

Best case is when the first two numbers are the pair. The map can grow to n entries.

Key idea

• For each nums[i], the only partner that works is need = target - nums[i].
• A hash map from value to index answers "have I seen need?" in O(1).
• Check the map before inserting nums[i], so an element never pairs with itself.
• One pass is enough: when the second element of the pair arrives, the first is already in the map.

Common mistakes

• Inserting before checking lets [3, 2, 4], target = 6 return [0, 0] (using 3 twice).
• Sorting first loses the original indices unless you carry them along.
• The brute-force double loop is O(n²); interviewers expect the hash map version.
• Returning values instead of indices.

Solution

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) {
            int j = seen.get(need);
            return new int[]{j, i};
        }
        seen.put(nums[i], i);
    }
    return new int[]{};
}

def twoSum(nums: List[int], target: int) -> List[int]:
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        auto it = seen.find(need);
        if (it != seen.end()) {
            return {it->second, i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

Edge cases

Each one has its own trace in the interactive view.