Two Sum

return array of two whose sum equals to target

Two Sum

Problem

You are given an array of integers nums and an integer target. Return the indices of the two numbers that add up to target.

• Each input has exactly one solution.
• You cannot use the same element twice.
• You can return the answer in any order.

Examples

Example 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

• nums[0] + nums[1] = 2 + 7 = 9, so we return [0, 1].

Example 2

Input: nums = [3,2,4], target = 6
Output: [1,2]

• nums[1] + nums[2] = 2 + 4 = 6.
• We cannot use 3 + 3, because there is only one 3 in this array.

Example 3

Input: nums = [3,3], target = 6
Output: [0,1]

• There are two different 3 values, at index 0 and index 1. Together they make 6.

Main Idea

For each number, we ask one question: "Have I already seen the number that completes the target?"

• For the current number nums[i], the number we need is target - nums[i]. We call it moreNeeded.
• We keep a hash map of numbers we have already seen. The key is the number, and the value is its index.
• If moreNeeded is in the map, we found the pair. We return its saved index and the current index i.
• If it is not in the map, we save the current number and its index, and move on.

A hash map can check "is this number here?" in O(1) time. So we do not need a second loop.

Note: We check the map before we save the current number. This way, we never use the same element twice.

Brute Force (For Comparison)

The simple way is to check every pair of numbers with two loops.

var twoSum = function (nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }

    return [];
};

Complexity

• Time Complexity: O(n²)
  • For each number, we check all the numbers after it.
• Space Complexity: O(1)
  • We use only a few variables.

Solution: Hash Map (One Pass)

var twoSum = function (nums, target) {
    let hash = new Map();

    for (let i = 0; i < nums.length; i++) {
        let moreNeeded = target - nums[i];

        // the number we need was already seen
        if (hash.has(moreNeeded)) {
            return [hash.get(moreNeeded), i];
        }

        // save the current number and its index
        hash.set(nums[i], i);
    }

    return [];
};

How the Code Works

Step 1: Create the map

• hash stores the numbers we have seen so far.
• The key is the number. The value is its index.

Step 2: Read each number

• moreNeeded = target - nums[i] is the partner we are looking for.
• If hash.has(moreNeeded) is true, the partner was seen earlier.
  • We return [hash.get(moreNeeded), i]. The first value is the partner's index. The second value is the current index.
• Otherwise, we save nums[i] with its index i and continue.

Step 3: Return an empty array

• The problem says there is always one solution, so we should never reach the last line.
• return [] is only a safe fallback.

Dry Run

Let us take nums = [2, 7, 11, 15] and target = 9.

The answer is [0, 1].

Now let us take nums = [3, 3] and target = 6.

• At i = 0, the map is empty, so the same element is not used twice.
• At i = 1, the first 3 is in the map, so we get the answer.

Complexity

• Time Complexity: O(n)
  • n is the length of the array.
  • We go through the array only once.
  • Each has, get and set on the map takes O(1) time on average.
• Space Complexity: O(n)
  • In the worst case, we save almost all numbers in the map before we find the pair.

Comparison

Summary

• For each number, we look for its partner: target - nums[i].
• A hash map remembers the numbers we have seen and their indexes.
• We check the map before saving the current number, so the same element is never used twice.
• This gives the answer in one pass.
• The hash map solution runs in O(n) time and uses O(n) space. It trades some extra memory for much better speed than brute force.