# Two Sum Algorithm in JavaScript (NodeJS)

*Last updated February 07, 2020*

I’m going to start solving algorithm challenges and writing about my methods in varrying languages from LeetCode. I’ll probably focus on JavaScript and C/C++. This is the first problem I’ve ever attempted. I’ll focus on harder one’s from here on out.

## Two Some Problem

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

## My solution

A brute force approach would be to iterate over the array twice:

- Loop over every element
- Loop over every other element, comparing sum of element A target to element B

This would look something like:

for (let a = 0, a < nums.length; a++) { // loop over every elementfor (let b = a + 1; b < nums.length; b++) { // loop over every *other* elementif (nums[b] === target - nums[a]) return [a, b;}}

This brute force approach would have a time complexity of O(n^2). Why? Because
for every element n we look up, we interate the array twice. But hash tables have
constant time for looking up elements. So if we implement a hash table to store
the elements, we can reduce the time complexity to O(n) because we only iterate
the number array once to store the elements in the hash table. A `Map`

in JavaScript
is a specific type of object with `set`

, `get`

, and `has`

methods, i.e. a hash table.

// nums = [4, 3, 6, 1]// target = 9const hashTable = new Map() // create an empty hash table// 1st iterationfor (let i = 0; i < nums.length; i++) {// i = 0const complement = target - nums[i] // complement == 9 - 4if (hashTable.has(complement))// 5 doesn't exist in hash tablereturn [hashTable.get(complement), i] // doesn't runhashTable.set(nums[i], i) // store [4 the value, 0 the index] in the hash table}// 3rd iterationfor (let i = 0; i < nums.length; i++) {// i = 2const complement = target - nums[i] // complement == 9 - 6if (hashTable.has(complement))// 3 exists in hash tablereturn [hashTable.get(complement), i] // return 3s index, and current index 2hashTable.set(nums[i], i) // doesn't run}

It’s important to note the difference between `hashTable.has`

and `hashTable.get`

.
`has`

checks the key of the hash table, and get returns the value of the hash table
at the given key.

hashTable = {key: value4: 0, // has checks against 43: 1 // get returns 1}

Using a hash table takes up more memory, but reduces the time complexity and the run-time in larger datasets. The brute force approach doesn’t take up any extra memory because we use the original array passed in as a parameter. This would have a space complexity of O(1). Whereas, the hash table approach requires creating a new record for every element resulting in a space-complexity of O(n).

Hashing uses a varible of set size to map to information of any size

JavaScript Map’s store information in the order it is entered, which resembles a stack data structure more than a hash table. However, it assigns the entered element a index which is the “hash function.” In the future, I plan on translating the JavaScript solutions into C and breaking down these data structures at a deeper level.

*I enjoy engineering software and writing about it. Follow me on Twitter for updates!*