LESSON 235 OF 338 · HASH TABLE

Two Sum in Go: O(n) with a Hash Map

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input will have at most one solution, and you may not use the same index twice.

In case no solution exists, return [-1, -1]

Example:

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

Note:

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

Hints:

This 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 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 there 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

Guided

Ctrl + Enter to check

Two Sum in Go, explained

Problem overview

The function twoSum takes a slice of integers, nums, and a target. It returns the indices of two numbers at different positions that add up to target, or [-1, -1] when no pair exists. There is at most one solution, and the same index cannot be used twice.

For nums = [2, 7, 11, 15] and target = 9, the values 2 and 7 at indices 0 and 1 add up to 9. This solution returns the pair as [1, 0]: the index of the later element comes first, then the index of the earlier one.

The statement requires O(n) time and O(n) extra space.

Approach: remember what you have seen

The brute-force approach tries every pair of indices with two nested loops, which is O(n²). To remove one loop, fix the later element of the pair, nums[i]. Its partner must equal target - nums[i] and sit somewhere to its left. Asking "is this value among the elements already seen?" is a lookup, and a hash map answers it in O(1).

The map must also give back the partner's position, so store each value together with its index: the key is the number, the value is its index. For each i from left to right, first look for target - nums[i] in the map. If it is there, the answer is i and the stored index. If not, record nums[i] with index i and move on.

On the example: at i = 0 the needed value is 7, the map is empty, so 2 is stored with index 0. At i = 1 the needed value is 9 - 7 = 2, which is in the map with index 0, so the function returns [1, 0].

Step by step

Create the map indexOfValue with make, of type map[int]int. It remembers where each value was last seen.
Loop over the indices with for i := range nums. With one variable, range over a slice gives just the index.
Look up the complement in an if with the comma-ok form, discarding the stored value and keeping the boolean exists. The lookup has to use comma-ok because the value 0 is a legitimate index.
On a hit, return a slice holding i and the stored index.
Otherwise store the current element after the check. Storing it first would let an element pair with itself.
Return []int{-1, -1} after the loop.

The solution in Go

func twoSum(nums []int, target int) []int {
    indexOfValue := make(map[int]int)
    for i := range nums {
        if _, exists := indexOfValue[target - nums[i]] ; exists {
            return []int{i, indexOfValue[target - nums[i]]}
        }
        indexOfValue[nums[i]] = i
    }
    return []int{-1, -1}
}

The Go details:

Comma-ok in the if. The statement before the semicolon runs first, and exists is visible only inside the if and its branches. Reading a missing key would give 0, which could be mistaken for index 0, so the boolean is what decides.
Slice literals. []int{i, x} builds a new slice of two integers.
Why make. A nil map cannot be written to; make(map[int]int) creates a usable one.

Complexity

Time: O(n). One pass, with a constant number of map operations per element, each O(1) on average.

Space: O(n). The map can hold one entry per element.

Edge cases and common mistakes

Equal values. [3, 3] with target 6 returns [1, 0]. The first 3 is stored before the second one is examined, so the two are different indices.
Using one element twice. [3, 4] with target 6 returns [-1, -1]. Because the current element is stored after the lookup, the 3 is never matched with itself.
Empty input. The loop does not run and the function returns [-1, -1].
Index order. The later index comes first: [3, 2, 4] with target 6 returns [2, 1].
Negative numbers and zero. [-3, 4, 3, 90] with target 0 returns [2, 0], and [0, 0] with target 0 returns [1, 0].
Repeated values. If a value occurs several times, the map keeps the latest index for it. With at most one valid pair, that is enough.

Testing

[2, 7, 11, 15], target 9 gives [1, 0].
[3, 3], target 6 gives [1, 0].
[3, 4], target 6 gives [-1, -1].
[1, 2, 3], target 100 gives [-1, -1].
[], target 6 gives [-1, -1].

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free