Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to the 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.

Example 1

Input: nums = [17,2,7,15], target = 9
Output: [0,2]

Explanation

We can add 2 and 7 to get 9, i.e, nums[0] + nums[2]. Hence the output will be [0,2]

Example 2

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3

Input: nums = [3,3], target = 6
Output: [0,1]

Solution

Brute force

So, we need to find out two integers X and Y such that their sum is equal to the target integer.

Let's start with all the possibilities we can have. Starting with X=17, Y can be 2,7 or 15. Similarly for X=2, Y can be 17,7 or 15, and so on.

X = 17
    Y = 2     => X+Y = 19
    Y = 7     => X+Y = 24
    Y = 15    => X+Y = 32

X = 2
    Y = 17    => X+Y = 19
    Y = 7     => X+Y = 9
    Y = 15    => X+Y = 17

X = 7
    Y = 17    => X+Y = 24
    Y = 2     => X+Y = 9
    Y = 15    => X+Y = 22

X = 15
    Y = 17    => X+Y = 32
    Y = 2     => X+Y = 17
    Y = 7     => X+Y = 22

When X=2 and Y=7, we found the answer as X+Y will be equal to target which is 9.

Pseudo Code

for i=0 to (n-1):
    for j=0 to (n-1):

        if I equal j :
            // we can't use the same element twice
            continue

        x = nums[i]
        y = nums[j]

        if x + y equals target:
            return [i,j]

Here's the implementation of the above pseudo-code in Golang

func twoSums(nums []int, target int) []int {

    numLen := len(nums)

    for i:=0; i<numLen; i++ {
        for j:=0; j<numLen; j++ {
            if i==j {
                // we can't use same element twice
                continue
            }
            x := nums[i]
            y := nums[j]

            if x+y == target {
                //we found the answer
                // return the indices
                return []int{i,j}
            } 
        }
    }

    return []int{-1,-1}
}

You can find the complete code here

The above code has run time complexity of O(n^2) and space complexity O(1). We can optimize the run time complexity of the above code by sorting the nums array.

Optimized approach I

In the previous approach, we were picking an X from the nums array and searching for the Y, i.e, Target-X in the nums array using a nested loop. We can improve on the search operation if the nums array was sorted. We can use binary search to find the value of Y. If Y is present in the nums array, that means we have a pair X, Y such that X+Y=target.

Pseudo Code

1. Sort nums array
2. Search for X and Y

        for i=0 to (n-1):

            y = target - nums[i]
            yIndex = binarySearch(nums, y)
            if yIndex != -1:
                return [i,yIndex]
        return [-1,-1]

Here's the implementation of the above pseudo-code in Golang

func twoSums(nums []int, target int) []int {

    for i := 0; i < len(nums); i++ {
        y := target - nums[i]
        yIndex := binarySearch(&nums, y, 0, len(nums))
        if yIndex == -1 || yIndex == i {
            continue
        } else {
            return []int{i, yIndex}
        }
    }
    return []int{-1, -1}
}

You can find the complete code here

The above code has run time complexity of O(N log N) and space complexity O(1).

Optimized approach II

We can further improve the solution if we can reduce the search time for the Y element. So let's first discuss what are the different search algorithms/data structures we can use to reduce the search time of Y.

• Linear Search We can do a linear search for key elements on a given array. It will cost us O(N), where N is the number of elements in the array.
• Binary Search We can do a binary search for the key element, but we will need to sort the array first. Considering the array is already sorted, it will cost O(log N)
• Hash Map Searching a key in a map takes constant time, i.e, O(1).

So if we somehow use the hashmap, we will reduce the search time of Y to O(1). Hence, reducing the overall time complexity of our code to O(N)

Pseudo Code

1. Create a map having the key of type int and value of int
       # key to be used to store the value of Y
       # value to be used to store the index itself

2. Search for X and Y

        for i=0 to (n-1):

            x = nums[i]
            y = target - x

            flag,yIndex = map.get(y)

            if flag == true:
                return [i,yIndex]
            else:
                map[x] = i

        return [-1,-1]

Explanation

nums  = [5,2,1,9,0,7]
target = 6
map    = {}

Let's take nums array as [5,2,1,9,0,7] and target as 6. Initially, our map would be empty.

i=0
    X = 5
    Y = target-X = 1
    map.get(1) // false
    map = {
        5: 0
    }

After the first iteration of the loop, X would be 5, and the Y we need is 1. Since map is empty, map.get(1) will return false. We will put the current X and its index on the map and continue with our next iteration.

i=1
    X = 2
    Y = target-X = 4
    map.get(4) // false
    map = {
        5: 0
        2: 1
    }

After the second iteration of the loop, X would be 2 and the Y we need is 4. The map doesn't have any key 4, map.get(4) will return false. We will again put the X on the map with its index as the value and we will continue with our next iteration.

i=2
    X = 1
    Y = target-X = 5
    map.get(5) // true
    return [0,2]

Now, X would be 1, and Y we need is 5. Since the map contains a key 5, map.get(5) will return true and the index value we stored earlier. We can return the current index i.e, 2, and the yIndex i.e, 0 as result.

Here's the implementation of the above pseudo-code in Golang

func twoSums(nums []int, target int) []int {
    yMap := make(map[int]int) 

    for i := 0; i < len(nums); i++ {

        y := target - nums[i]

        yIndex,ok := yMap[y]
        if ok {
           return []int{i, yIndex}
        } else {
            yMap[nums[i]] = i
        }
    }

    return []int{-1, -1}
}

You can find the complete golang implementation here

Conclusion

In this guide, we saw 3 different ways to solve the classic data structure and algorithm problem, Two Sum. We saw how we can improve the brute force solution using sorted array and binary search to find the elements. Further, we explored how we can improve the solution using maps.

I hope this article was helpful and you learned something new. If you have any queries, feel free to ask in the comments.