Two Sum

The problem

You are given an array nums of whole numbers (call its length n) and a number target. Exactly two numbers in the array, at two different positions, add up to target. Return their two indexes.

There is always exactly one such pair. You may return the two indexes in either order.

Example 1

Input: nums = [5, 9, 1, 7, 4], target = 11

Output: [3, 4]

nums[3] + nums[4] = 7 + 4 = 11. No other pair adds up to 11.

nums

5091127344

target

11

Example 2

Input: nums = [3, 3], target = 6

Output: [0, 1]

The two 3s sit at different positions, so they may be used together.

Example 3

Input: nums = [-2, 8, 6], target = 4

Output: [0, 2]

−2 + 6 = 4. Negative numbers work like any other.

Constraints

• 2 ≤ n ≤ 10,000
• −1,000,000,000 ≤ nums[i] ≤ 1,000,000,000
• −1,000,000,000 ≤ target ≤ 1,000,000,000
• Exactly one pair adds up to target.

Clarifying questions

Do we return the values or the indexes?

The indexes. That matters: sorting the array would lose them.

Can one number be used twice?

No. The two indexes must differ. Two equal values at different indexes are fine, like [3, 3].

What if no pair works?

That cannot happen. The problem promises exactly one answer.

Can the sum overflow?

No. The largest sum is 2,000,000,000, which still fits in a 32-bit integer.

Spot the pattern

Once you pick one number, its partner is fixed: it must be target − number. So the real question for each number is “have I already seen target − number, and where?”. A hash map from value to index answers that in one step. That is the hashing pattern.

Solutions

Brute forceO(n²)Hash mapO(n)

Show all

Sorting plus two pointers also works, in O(n log n). But sorting moves the numbers and we need their original indexes, so it adds work and is still slower than the hash map.

Brute force O(n²)

The idea

Try every pair of positions i < j. If nums[i] + nums[j] equals the target, return [i, j].

There is exactly one answer, so the search always ends with it. But with n numbers there are about n × n / 2 pairs to try.

Walkthrough

nums

5091127344

target

11

1. for i in range(len(nums)):
2. for j in range(i + 1, len(nums)):
3. if nums[i] + nums[j] == target:
4. return [i, j]

Try every pair i < j and add the two numbers. Stop when a sum equals 11.

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: try every pair of positions.
    // About n * n / 2 pairs, so O(n^2) time and O(1) extra memory.
    public int[] twoSum(int[] nums, int target) {
        int numsLength = nums.length;
        for (int i = 0; i < numsLength; i++) {
            // j starts after i: a number cannot pair with itself,
            // and pairs with smaller j were tried when i was smaller.
            for (int j = i + 1; j < numsLength; j++) {
                if (nums[i] + nums[j] == target) return new int[] { i, j };
            }
        }
        // The problem promises one answer, so this line is never reached.
        return new int[0];
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line adds two numbers and compares the sum. It sits inside two loops. One addition and one comparison do not grow with n, so each run is 1 step.

   1. for i in range(len(nums)):
   2. for j in range(i + 1, len(nums)):
   3. if nums[i] + nums[j] == target:
   4. return [i, j]

2. 2 Count the runs on Example 1

   Example 1 has 5 numbers. Its answer is the very last pair, (3, 4), so the search tries every pair: 4 for i = 0, 3 for i = 1, 2 for i = 2 and 1 for i = 3.

   4 + 3 + 2 + 1 = 10 runs. That is the worst case: the answer sits in the last pair checked.

   i	0	1	2	3	4
   pairs tried	4	3	2	1	0

   pairs tried

   4 + 3 + 2 + 1 = 10

3. 3 Write the count for any n

   With n numbers, index 0 pairs with n − 1 others, index 1 with n − 2, and so on down to 1:

   (n − 1) + (n − 2) + … + 1 = n × (n − 1) / 2 = ½n² − ½n

   Check it with Example 1: 5 × 4 / 2 = 10.

4. 4 Keep only the part that grows fastest

   • Drop the −½n. Next to ½n² it soon stops mattering.
   • Drop the ½. Halving every count does not change how fast it grows. When n doubles, the work still grows 4 times.

   What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code creates only i and j, whatever n is. The space is O(1).

   ij

Hash map O(n)

The idea

Walk the array once, from left to right. For each number, work out the partner it needs: need = target − number. Then ask a hash map: “have I seen need before, and at which index?”. A hash map stores pairs (here, value and index) and finds a value in one step on average.

If the map has need, we are done. If not, store number with its index and move on. Store number after the check, so a number never pairs with itself.

Why it never misses the answer: call the answer’s indexes j < i. When the loop reaches i, the number at j is already in the map, so the lookup finds it.

Walkthrough

nums

5091127344

seen (value → index)

empty

1. seen = {}
2. for i, number in enumerate(nums):
3. need = target - number
4. if need in seen:
5. return [seen[need], i]
6. seen[number] = i

Start with an empty hash map. It will remember each number we pass and where it was.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Hash map: for each number, look up the partner it needs.
    // One pass with O(1) lookups, so O(n) time and O(n) memory.
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // value -> index
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            // The partner, if it exists before i, is already in the map.
            if (seen.containsKey(need)) return new int[] { seen.get(need), i };
            // Store nums[i] after the check, so it never pairs with itself.
            seen.put(nums[i], i);
        }
        // The problem promises one answer, so this line is never reached.
        return new int[0];
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop does one subtraction, one map lookup and at most one map insert. Each of those takes one step on average, so each run counts as 1 step. There is one loop.

   1. seen = {}
   2. for i, number in enumerate(nums):
   3. need = target - number
   4. if need in seen:
   5. return [seen[need], i]
   6. seen[number] = i

2. 2 Count the runs on Example 1

   Example 1 has 5 numbers. The loop runs once for each, and the 5th run finds 7 in the map.

   5 runs.

   run	1	2	3	4	5
   number	5	9	1	7	4
   need	6	2	10	4	7
   in map?	no	no	no	no	yes

3. 3 Write the count for any n

   The loop visits each number at most once, so in the worst case it runs:

   n times

   Check it with Example 1: 5 numbers, 5 runs.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is already n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The map is the extra memory. In the worst case the answer is the last pair, so every number but one goes into the map first. That is n − 1 entries, so the space is O(n). The few other variables add a fixed amount.

   seen (up to n entries)inumberneed

Common mistake

Filling the map before the loop

If you first put every number in the map and then search, a number can find itself. With nums = [3, 5] and target = 6, the 3 finds its own 3 and returns [0, 0]. Check, then store, in one pass.

Tested at the limits

2,000 random arrays of 2 to 8 small numbers, with repeats and negatives, and exactly one pair that adds up to the target. The brute force and the hash map gave the same answer every time.

Largest inputs	Result
10,000 numbers (the most allowed), all different, with the only pair at the last two places, so the search runs to the end. Hash map.	Under 0.01 s, and about 0.6 MB of extra memory: the map holds up to 10,000 numbers, which is the O(n) space.
2,000 numbers, pair at the end. Brute force, about 2 million pairs.	0.09 s. At 10,000 numbers it would check 50 million pairs, which is why the hash map matters.