TwoSum

Short Summary

Given an array of integers and a target, return the indexes of the values that add up to the target.

---

I/O Example

// inputArr := [3,2,4]
// target := 6

// output := myFunction(inputArr, windowSize)

// output = [1,2]

---

Explanation and Walk-through

Simple approach

In the simple approach, we can walkthrough the array in a nested loop and for each element, check if there's another element that adds up to the target.

    func twoSumSimple(input []int, target int) []int{
        for i:=0; i<len(input); i++{
            for j := i+1 ; j <len(input); j++{
                if input[i] + input[j] == target{
                    return []int{i, j}
                }
            }
        }
    }

Increasing efficiency

With the previous approach, we have O(n^2) runtime, since we essentially loop through every remaining item for every item. We can do better by keeping track of the visited items. For each item in the list, we need to be able to quickly lookup if we have seen another item that complements the current one. Since we need efficient lookups, we can use a hashtable. Golang has the builtin map data structure that fits this purpose.

So now, the algorithm becomes:

• Visit an item in the list.
• Calculate the complement
• Lookup if the complement exists in the table.
• If it does, return the complement's index and current index in that order. (since complement's index will be smaller)
• If it does not exists, add complement to the table, the key will be the complement and the value will be current index.
• Repeat

With this approach, we only have to do N lookups and N inserts in to the table, each of which will cost O(1) time with the map data structure.

func twoSum(nums []int, target int) []int {
	targetSet := map[int]int{}
	var complement int
	for i, v := range nums {
		complement = target - v
		if found, ok := targetSet[v]; ok {
			return []int{found, i}
		}
		targetSet[complement] = i
	}
	return nil
}

---

Extra comments

You can try it yourself on leetcode

---

Please comment or dm me if you have other questions or remarks.

Until next time,

Stay all in!

Reha S.

Sep 09 2022