Two Sum

How it works

We can solve the problem in a single pass by iterating through the array and checking if the complement of the current element exists in the hash map.

If it does, we return the indices of the current element and its complement. If not, we store the current element in the hash map. This guarantees that we will never use the same element twice, but we still check every element in the array.

Steps

1. Create a hash map to store the value and index of each element in the array.
2. Iterate through the array using index i and compute the complement of the current element, which is target - nums[i].
3. Check if the complement exists in the hash map.
4. If it does, return the indices of the current element and its complement.
5. If no such pair is found, return an empty array.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Using the Same Element Twice

You cannot use the same element twice to form a pair. When using a hash map, ensure you check that the found index differs from the current index, or use one-pass where you only look at previously seen elements.

Returning Values Instead of Indices

The problem asks for indices, not the values themselves. A common mistake is returning the two numbers that sum to the target rather than their positions in the array.

Handling Duplicate Values

When building a hash map with values as keys, duplicate values overwrite earlier indices. In the two-pass approach, this still works because you check indices[diff] != i. In the one-pass approach, you check for the complement before inserting the current element.

Wrong Complement Calculation

The complement should be target - nums[i], not nums[i] - target. Getting this backwards will search for the wrong value.

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index

        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> prevMap;

        for (int i = 0; i < n; i++) {
            int diff = target - nums[i];
            if (prevMap.find(diff) != prevMap.end()) {
                return {prevMap[diff], i};
            }
            prevMap.insert({nums[i], i});
        }
        return {};
    }
};