# JavaScript Algorithms: Two Sum (LeetCode)

# Description

**The problem is: **Given an array of integers, return **indices** of the two numbers such that they add up to a specific target.

You may assume that each input would have ** exactly** one solution, and you may not use the

*same*element twice.

**Example:**

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,

return [0,1].

# Solution

A good question to ask to an interviewer is — wether the array sorted or not. If it’s not sorted we can use two nested loops or hashmap, if we know that an array is sorted we can use another algorithm.

Let’s figure out how to solve this problem with an unsorted array.

**Runtime O(n²); Memory O(1):**

I’d call it a *brute force solution*. Or if we can’t use additional data structures this solution will be fine.

We can use two nested for loops, in the external we’re going through each array element (*i*), and in the second we are going through the rest of the items (*j = i + 1*) and check whether the sum equals to target.

For example, we have:

Let’s go ahead and implement this using JavaScript:

This works a hundred percent of the time, but the problem is — we have a loop inside another loop and it’s really slow.

Let’s say we have millions of nums, so we need to come up with a better solution. We can do that using HashMap:

**Runtime O(n); Memory O(n):**

The idea is to create a Map with all elements in the array. You can then

scan over the nums and check, for each element *nums[i]*, whether there’s another element *nums[j]* in the array where *nums[j] = target — nums[i]*.

The Map key will be the difference between *target* and *nums[i]* and the value will be index *i* in the array.

P.S. If we didn’t need to return indexes we would have used a Set.

For example, we have:

Let’s implement it using JavaScript:

In this case, we know that keys are only integers, therefore we can use Object as well. Let’s see how does it look like:

In case if the array is sorted we can use two pointers *left* and *right*. We know that is nothing that can be smaller than the first array item and there is nothing that can be bigger than the last array item. So, we can check if the sum is less than the target, we need to increment left and if the sum is bigger than the target, we should decrement the right pointer. And if *left* and *right* add up to target we can return *[left, right]*.

**Runtime O(n); Memory O(1):**

For example, we have:

JavaScript implementation:

Let’s summarize all of this:

— if you’re not allowed to use additional Data Structures and the array is not sorted — two nested loops is a good solution;

— if you need to come up with the fastest solution with an unsorted array — you should use Map;

— if you know that the array is sorted — use the two pointers technique;

Thanks for reading! Looking forward to your feedback. See you soon ✌️