# 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 + nums = 2 + 7 = 9,return [0, 1].`

## My solution

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

1. Loop over every element
2. 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 element  for (let b = a + 1; b < nums.length; b++) { // loop over every *other* element    if (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 = 0  const complement = target - nums[i] // complement == 9 - 4  if (hashTable.has(complement))    // 5 doesn't exist in hash table    return [hashTable.get(complement), i] // doesn't run  hashTable.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 = 2  const complement = target - nums[i] // complement == 9 - 6  if (hashTable.has(complement))    // 3 exists in hash table    return [hashTable.get(complement), i] // return 3s index, and current index 2  hashTable.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: value  4: 0, // has checks against 4  3: 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.