two-sum-algorithm.js

// assumption - each input would have exactly one solution, and the same element may not be used twice in the input array

// brute force solution
function twoSumNaive(array, sum) {
  let indices = []

  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] + array[j] === sum) {
        indices.push(i)
        indices.push(j)
      }
    }
  }

  return indices
}

// more officient solution
// uses a hashtable data structure instead of keeping input as an array
// so we can instantly look up values instead of traversing through every element
function twoSumOptimized(array, sum) {
  let indices = []
  let map = new Map()

  // set map entries
  for (let i = 0; i < array.length; i++) {
    map.set(array[i], i)
  }

  // iterate through array
  for (let j = 0; j < array.length; j++) {
    let secondNumber = sum - array[j]

    // if map has an entry with secondNumber as key
    // AND if the entry value is not equal to current array index i.e. not comparing with self
    if (map.has(secondNumber) && map.get(secondNumber) !== j) {
      indices.push(j)
      indices.push(map.get(secondNumber))
    }
  }

  return new Set(indices)
}

console.log(twoSumOptimized([1, 2, 3, 4, 5], 3))