Two Sum

Difficulty: #easy

This is based off the problem found on leetcode (Two Sum).

It has the following problem text,

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Solutions

Optimal solution

To solve this optimally, we’d create a hash map where we map the value to the index; i.e. our key would be value at the index, and the index would be the value of our hash map. We would populate this hash map as we iterated over the input array. Doing this prevents the need to add additional logic to prevent checking the current index isn’t the index we’re on. The runtime complexity in this case would be $O(n)$ as we only have to iterate over the input once. However - we’d have a space complexity of $O(n)$ as well, because we’re creating a hash map to store and keep track of the input values and their indexes.

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}

        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i

        return [0]

Brute force solution

To solve this using brute force, we’d scan through each element and check if they give us our target. We’d use a loop over each element, with a sub loop iterating over each next element against the first; if the sum of the two match our target - we’d return. Because we’re going over each element at a worse case scenario of twice, the runtime complexity of this algorithm would be $O(n^2)$, however the space complexity would be $O(1)$ as we only need the collection itself.

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums) - 1):
            for ii in range(1, len(nums)):
                if nums[i] + nums[ii] == target:
                    return [i, ii]
        return [0]

Golang solution using a hash map with unit tests

This is an example implementation in Golang, using the hash map version of the solution,

solution.go

package main

func twoSum(nums []int, target int) []int {
	prevNums := make(map[int]int)

	for i, num := range nums {
		check := target - num
		if n, exists := prevNums[check]; exists {
			return []int{n, i}
		}
		prevNums[num] = i
	}

	return []int{0}
}

solution_test.go

package main

import (
	"reflect"
	"testing"
)

func TestTwoSum(t *testing.T) {
	tests := []struct {
		nums   []int
		target int
		want   []int
	}{
		{[]int{2, 7, 11, 15}, 9, []int{0, 1}},
		{[]int{3, 2, 4}, 6, []int{1, 2}},
		{[]int{3, 3}, 6, []int{0, 1}},
		{[]int{-3, 4, 3, 90}, 0, []int{0, 2}},
		{[]int{-1, -2, -3, -4, -5}, -8, []int{2, 4}},
		{[]int{1, 2, 3}, 7, []int{0}},
		{[]int{}, 0, []int{0}},
		{[]int{1}, 1, []int{0}},
	}

	for _, tt := range tests {
		t.Run("", func(t *testing.T) {
			got := twoSum(tt.nums, tt.target)
			if !reflect.DeepEqual(got, tt.want) {
				t.Errorf("twoSum(%v, %d) = %v; want %v", tt.nums, tt.target, got, tt.want)
			}
		})
	}
}

You can run the above with go test assuming you’ve created a go module, and have two separate files, solution.go, and solution_test.go.