# 1. Two Sum

LeetCode Problems

In this tutorial we will solve 1. Two Sum problem from leetcode.

## Table of Content

Reference: 1. Two Sum

## Problem statement

In this problem we have an input integer array `nums` and we have an integer `target`. We have to find the indices of two numbers in the given array that add up to target and we cannot use the number at a given index more than once. We are also told in the problem statement that the input would always have exactly one solution.

Example from leetcode.

``````Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]

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

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

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
``````

In example 1, we can see number at index 0 and 1 adds up to 9.

In example 2, we can see number at index 1 and 2 adds up to 6.

And in example 3, we have number at index 0 and 1 adding up to 6.

## Approach

To solve this problem we can take help of hash map and save the number and its index as we traverse the input array.

``````Input: nums = [2,7,11,15], target = 9

hashmap = {}

index =  0   1   2    3
nums  = [2,  7,  11,  15]
^

neededNumber = target - currentNumber
= 9 - 2
= 7

7 is not present in the hashmap, add current number 2 and its index 0.
hashmap = {
2: 0
}

index =  0   1   2    3
nums  = [2,  7,  11,  15]
^

neededNumber = target - currentNumber
= 9 - 7
= 2

2 is present in the hashmap, fetch the index of 2 and return the result.
``````

## Code

JavaScript

``````/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let hm = new Map();
for(let i = 0; i < nums.length; i++) {
const currentNumber = nums[i];
const neededNumber = target - currentNumber;
const indexOfNeededNumberIfExists = hm.get(neededNumber);
if (indexOfNeededNumberIfExists !== undefined) {
return [indexOfNeededNumberIfExists, i];
}
hm.set(currentNumber, i);
}
};``````

## Complexity

Time complexity: O(n)

In the worst case, we will traverse the whole array and if there are n elements then our time complexity will be O(n).

Space complexity: O(n)

In the worst case, our hash map will save n elements. Thus the space complexity will be O(n).