Start learning free

LESSON 358 OF 675 · HASH TABLE

Two Sum

Practice O(n)

You get an array of integers nums and a number target.

Return the indices of two numbers that add up to target.

The two indices must be different. You can return them in either order.

If no pair adds up to target, return [-1, -1].

Example 1:

Input: nums = [5, 12, 3, 8], target = 15
Output: [1, 2]
Explanation: nums[1] + nums[2] = 12 + 3 = 15

Example 2:

Input: nums = [6, 1, 6], target = 12
Output: [0, 2]
Explanation: nums[0] + nums[2] = 6 + 6 = 12
The two 6s are at different indices.

Example 3:

Input: nums = [5, 1, 3], target = 10
Output: [-1, -1]
Explanation: No pair adds up to 10.
5 + 5 would use index 0 twice.

Constraints:

  • 2 to 1,000,000 numbers.
  • Each number fits in a 32-bit signed integer.
  • The target fits in a 32-bit signed integer too.
  • At most one pair adds up to the target.

Note:

Your algorithm should run in O(n) time and use O(n) space.


Hints:

This is the type of problem where we optimize the brute force approach to get the optimal one. The brute force approach took O(n^2) time because we had two nested for loops, one for i and another one for j. In order to get O(n), we have to reduce this to only one for loop, so we should fix only one index, let it be j, the index of the second number. We will try out each possible j, and for each of them we should check if there is an index i < j such that nums[i] + nums[j] == target: 
for each j : 0 -> n - 1:
	// We know nums[j]. Find some index i < j such that nums[i] + nums[j] == target.
How can we find that index in O(1)?

nums[i] + nums[j] == target ⇔ nums[i] == target - nums[j]. So for each j, we should look for an element equal to target - nums[j] from the left of j. Is there a data structure that allows us to look for an element in a collection in constant time? How can we use it here?

That data structure is the Hash Map. We can have a Hash Map where we insert all the elements nums[j] we iterate on during the for loop. In this way, for each j, we can look in the Hash Map to see if there is some element of value target - nums[j] and if so, we found a solution: 
for each j : 0 -> n - 1:
	- Look for target - nums[j] in the Hash Map. If it exists, we found the solution.
	- Otherwise, insert nums[j] into the Hash Map and continue with the for loop.
I know the code above is not perfect. Hash Maps work with pairs (key => value), we cannot just insert a nums[j] into a Hash Map. What should we actually insert in this hash map? What are the keys and what are the values?

The problem with the code above is that we just check if there is an element equal to target - nums[j]. If so, we have a solution, but that's not enough. The problem asks us to return the indices of those elements and we only know of them: j. Can we adapt the solution such that if for some j there is an element equal to target - nums[j], we can also get its index?

The pairs in the Hash Map should be nums[j] => j so that for each element we insert, we can also get its index: 
for each j : 0 -> n - 1:
	if target - nums[j] in indexOfValue:
		return [indexOfValue[target - nums[j]], j]
	indexOfValue[nums[j]] = j
return [-1, -1]

STEP 1 OF 6
    Ctrl + Enter to check