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:

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 ✌️

Software Engineer | Frontend Developer | React Developer | JavaScript Developer https://anatolii.tech/

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store