### Problem

Write a function:

`function solution(nums, target);`

that, 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.

#### Examples

- Given
`nums = [2,7,11,15], target = 9`

, the function should return`[0,1]`

. - Given
`nums = [3,2,4], target = 6`

, the function should return`[1,2]`

. - Given
`nums = [3,3], target = 6`

, the function should return`[0,1]`

.

Write an efficient algorithm for the following assumptions

`2 <= nums.length <= 103`

`-109 <= nums[i] <= 109`

`-109 <= target <= 109`

**Only one valid answer exists.**

You can find the link of the question here.

## Solutions

##### Brute force solution

```
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
function solution(nums, target) {
if (nums.length < 2) {
return [];
}
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
```

**BigO Notation**

Time | Space |
---|---|

O(N^2) | O(1) |

##### Optimal Solution

```
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
function solution(nums, target) {
if (nums.length < 2) {
return [];
}
const numsMap = {};
for (let i = 0; i < nums.length; i++) {
let curMapVal = numsMap[nums[i]];
if (curMapVal >= 0) {
return [i, curMapVal];
} else {
const numberToFind = target - nums[i];
numsMap[numberToFind] = i;
}
}
return [];
}
```

**Explanation**
We have our `numsMap`

which is a **hashmap** that contains `key/value`

pairs. We create these `key/value`

pairs based on figuring out what the `numberToFind`

is when we look at each number in the array. The key is the `numberToFind`

and the value is the index of the number we're currently looking at. This means that as we go through the array, we compare each number to see if it matches one of the `numberToFind`

we've already created. If it already exists in our hashmap, then the value we get will be the index of element in the array that created the `numberToFind`

which gives us our answer!

**BigO Notation**

Time | Space |
---|---|

O(N) | O(N) |

### Solution in Python

```
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
if len(nums) < 2:
return []
numsMap = {}
for i, num in enumerate(nums):
curMapVal = numsMap.get(num)
if curMapVal is not None:
return [curMapVal, i]
break
else:
diff = target - nums[i]
numsMap[diff] = i
return []
```

The solutions above are pretty self-explanatory.

💌 If you’d like to receive more coding solutions in your inbox, you can sign up for the newsletter here.

## Discussions