15 min to read

Two Sum

Featured image

In this article, we bring you another challenge from AlgoDaily called Two Sum.

We recommend trying to complete the challenge yourself, before reading our explanation, here.

The Challenge

Given an array of integers, return the indices of the two numbers in it that add up to a specific goal number.

So let’s say our goal number was 10. Our numbers to sum to it would be 3 and 7, and their indices 1 and 3 respectively.

let arr = [1, 3, 6, 7, 9];
let goal = 10;
twoSum(arr, goal); // [1, 3]

You may assume that each input would have exactly one solution. Additionally, you may not use the same element twice. For example, if given a slice of [1,3] and a goal of 2, you cannot use 1 twice and return [0,0] as your answer.

Test Cases

Learn to complete this challenge using:

if you don’t see your favourite language here, feel free to leave a comment and tell us which one you’d like us to cover or check back at another time and see if we’ve added it.

The solutions and test cases for this challenge can be found on our GitHub account.

Go

First, let’s define our test cases in a file called twosum_test.go. We’ll use a Table Driven Test to keep our test cases free of unnecessary duplication and keep them easy to read/maintain.

// twosum_test.go

package twosum

import (
	"fmt"
	"reflect"
	"testing"
)

func TestTwoSum(t *testing.T) {
	testCases := []struct {
		nums     []int
		goal     int
		expected []int
	}{
		{
			nums:     []int{1, 9, 13, 20, 47},
			goal:     10,
			expected: []int{0, 1},
		},
		{
			nums:     []int{3, 2, 4, 1, 9},
			goal:     12,
			expected: []int{0, 4},
		},
		{
			nums:     []int{},
			goal:     10,
			expected: []int{},
		},
	}
	for ix, tC := range testCases {
		t.Run(fmt.Sprintf("test %d - TwoSum should return expected output", ix), func(t *testing.T) {
			output := TwoSum(tC.nums, tC.goal)

			if !reflect.DeepEqual(tC.expected, output) {
				t.Errorf("expected '%+v' to equal '%+v', but it did not", output, tC.expected)
			}

		})
	}
}

Next, let’s create our TwoSum function declaration. We already know from the test description that we expect a slice of indices and a goal, as input, and that we should return a slice of indices that sum up to the goal, or an empty slice if a match isn’t found.

package twosum

// TwoSum takes a slice of ints and an expected goal, and returns the
// indices that sum together to reach that goal, or an empty slice otherwise.
func TwoSum(nums []int, goal int) []int {
	return []int{}
}

Note: going forward we will omit the package and import statements, but they can be found on our GitHub account.

Running our tests we get two expected failures, and one passing test (because we hardcoded a response of an empty slice).

go test -v ./...
=== RUN   TestTwoSum
=== RUN   TestTwoSum/test_0_-_TwoSum_should_return_expected_output
=== RUN   TestTwoSum/test_1_-_TwoSum_should_return_expected_output
=== RUN   TestTwoSum/test_2_-_TwoSum_should_return_expected_output
--- FAIL: TestTwoSum (0.00s)
    --- FAIL: TestTwoSum/test_0_-_TwoSum_should_return_expected_output (0.00s)
        twosum_test.go:36: expected '[]' to equal '[0 1]', but it did not
    --- FAIL: TestTwoSum/test_1_-_TwoSum_should_return_expected_output (0.00s)
        twosum_test.go:36: expected '[]' to equal '[0 4]', but it did not
    --- PASS: TestTwoSum/test_2_-_TwoSum_should_return_expected_output (0.00s)
FAIL

We need to compare two indices at a time, to see if they sum up to the goal. For example, when given an input of [0,1,12,20,9] and 10 we could write down the logic like so:

Let’s print the indices out first, to make sure we’re getting the expected behaviour.

func TwoSum(nums []int, goal int) []int {
	for ix := range nums {
		for i := ix + 1; i < len(nums)-1; i++ {
			fmt.Printf("Outer index: %d, Inner index: %d \n", ix, i)
		}
	}

	return []int{}
}

Now let’s add another test case to our Table Driven Test (below).

{
	nums:      []int{0, 1, 12, 20, 9},
	goal:     10,
	expected: []int{1, 4},
},

And we’ll comment out the rest of the tests just to observe the Printf statements for our new test case:

go test -v ./...
=== RUN   TestTwoSum
=== RUN   TestTwoSum/test_0_-_TwoSum_should_return_expected_output
Outer index: 0, Inner index: 1 
Outer index: 0, Inner index: 2 
Outer index: 0, Inner index: 3 
Outer index: 0, Inner index: 4 
Outer index: 1, Inner index: 2 
Outer index: 1, Inner index: 3 
Outer index: 1, Inner index: 4 
Outer index: 2, Inner index: 3 
Outer index: 2, Inner index: 4 
Outer index: 3, Inner index: 4

Excellent, now all we need to do is check to see if the values equal our goal and, if they do, return the indices. If we never reach our goal (i.e. our loops end), we return an empty slice to signify that a match wasn’t found.

func TwoSum(nums []int, goal int) []int {
	for ix := range nums {
		for i := ix + 1; i < len(nums); i++ {
			if nums[ix]+nums[i] == goal {
				return []int{ix, i}
			}
		}
	}

	return []int{}
}

Let’s uncomment and run all of our test cases and make sure they all pass

go test -v ./...
=== RUN   TestTwoSum
=== RUN   TestTwoSum/test_0_-_TwoSum_should_return_expected_output
=== RUN   TestTwoSum/test_1_-_TwoSum_should_return_expected_output
=== RUN   TestTwoSum/test_2_-_TwoSum_should_return_expected_output
=== RUN   TestTwoSum/test_3_-_TwoSum_should_return_expected_output
--- PASS: TestTwoSum (0.00s)
    --- PASS: TestTwoSum/test_0_-_TwoSum_should_return_expected_output (0.00s)
    --- PASS: TestTwoSum/test_1_-_TwoSum_should_return_expected_output (0.00s)
    --- PASS: TestTwoSum/test_2_-_TwoSum_should_return_expected_output (0.00s)

Four passing test cases! But we’re not done yet! Although this solution works, we need to consider if it’s a “good” solution.

Because we’re using two loops, we’ve introduced the possibility that our code will need to process every element in our nums slice n number of times (where n is the length of the slice)!

Imagine if someone passed in a slice with a million elements, and how many loops we’d be running! We can characterise this Algorithmic Complexity as Quadratic or O(n^2), which is very well described here. Luckily, there is a better way!

First, let’s comment out all of our tests, like we did before, apart from the one below:

{
	nums:      []int{0, 1, 12, 20, 9},
	goal:     10,
	expected: []int{1, 4},
},

Next, we’re going to make a map of processed elements and will be constructed of the following:

func TwoSum(nums []int, goal int) []int {
	processed := make(map[int]int)

	for index, currentValue := range nums {
		currentSubtraction := goal - currentValue

		processed[currentSubtraction] = index
	}

	fmt.Printf("%+v", processed)

	return []int{}
}

Running our tests again will fail, because we’ve not implemented all of our logic yet, but we should see the output of our processed map.

=== RUN   TestTwoSum/test_0_-_TwoSum_should_return_expected_output
map[-10:3 -2:2 1:4 9:1 10:0]--- FAIL: TestTwoSum (0.00s)

Here we see the outputs of the goal (10) minus each element (0, 1, 12, 20 and 9) as the keys and their index positions as the values.

So how does this actually help us? Well, we know what the subtraction is of the current element, therefore we know what value we need in order to make the goal, we also know the subtractions of the elements that have come before it, so we can work out if we have an index that satisfies the TwoSum requirement.

That’s a really confusing statement, so let’s break it down step-by-step. First, let’s define what we mean by these statements:

Now, let’s go through the slice we’re using in our test case ([0, 1, 12, 20, 9] step-by-step:

1) Index 0, Value 0 - Current subtraction ( 10 - 0) = 10 - Required value to satisfy requirement (10 - 10) = 0 - Do we have an element in our map with a key of 0? No. 2) Index 1, Value 1 - Current subtraction (10 - 1) = 9 - Required value to satisfy requirement (10 - 9) = 1 - Do we have an element in our map with a key of 1? No. 3) Index 2, Value 12 - Current subtraction (10 - 12) = -2 - Required value to satisfy requirement (10 - -2) = 12 - Do we have an element in our map with a key of 12? No. 4) Index 3, Value 20 - Current subtraction (10 - 20) = -10 - Required value to satisfy requirement (10 - -10) = 20 - Do we have an element in our map with a key of 20? No. 5) Index 4, Value 9 - Current subtraction (10 - 9) = 1 - Required value to satisfy requirement (10 - 1) = 9 - Do we have an element in our map with a key of 9? Yes! So we return [1,4] which represents the index of the found item (1) and the current index (4).

And we can write this in code, using exactly the same logic, like so:

func TwoSum(nums []int, goal int) []int {
	processed := make(map[int]int)

	for index, currentValue := range nums {
		currentSubtraction := goal - currentValue
		requiredValue := goal - currentSubtraction


		ix,  ok := processed[requiredValue]
		if ok {
			return []int{ix, index}
		}

		processed[currentSubtraction] = index
	}

	return []int{}
}

Now, let’s uncomment all of our test cases and run them one final time:

$ go test -v ./...
=== RUN   TestTwoSum
=== RUN   TestTwoSum/test_0_-_TwoSum_should_return_expected_output
=== RUN   TestTwoSum/test_1_-_TwoSum_should_return_expected_output
=== RUN   TestTwoSum/test_2_-_TwoSum_should_return_expected_output
map[]=== RUN   TestTwoSum/test_3_-_TwoSum_should_return_expected_output
=== RUN   TestTwoSum/test_4_-_TwoSum_should_return_expected_output
=== RUN   TestTwoSum/test_5_-_TwoSum_should_return_expected_output
--- PASS: TestTwoSum (0.00s)
    --- PASS: TestTwoSum/test_0_-_TwoSum_should_return_expected_output (0.00s)
    --- PASS: TestTwoSum/test_1_-_TwoSum_should_return_expected_output (0.00s)
    --- PASS: TestTwoSum/test_2_-_TwoSum_should_return_expected_output (0.00s)
    --- PASS: TestTwoSum/test_3_-_TwoSum_should_return_expected_output (0.00s)
    --- PASS: TestTwoSum/test_4_-_TwoSum_should_return_expected_output (0.00s)
    --- PASS: TestTwoSum/test_5_-_TwoSum_should_return_expected_output (0.00s)
PASS

And now, we only ever loop through our nums slice once! We can characterise this Algorithmic Complexity as Linear or O(n), which is a much better solution.