LeetCode Problems

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

Reference: 1. Two Sum

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.

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.
```

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);
}
};
```

**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).

ADVERTISEMENT