Target Sums: A great interview programming problem with O(n^2) and O(n) solutions

target_sums.js

/*
* Target Sums: Given a distinct list of unordered integers and an integer known as the target
* sum, devise a function that outputs true if some combination of two numbers from the list can
* add up to the target sum. Otherwise, return false.
*/

// This solution is the typical brute force that executes in O(n^2)
// n = arr.length

function targetSums(arr, target) {
  for (var i=0; i<arr.length; i++) {                          // 1
    for (var j=0; j<arr.length; j++) {                        // n 
      if (((arr[i] + arr[j]) === target) && (i !== j)) {      // n^2  
        return true;                                          
      }
    }
  }
  return false;                                               // 1
}

// 1 + n + n^2 + 1
// O(n^2 + n + 2) ~= O(n^2)

// This is an innovative solution that I did not come up with that runs in O(n)

function targetSumsV2(arr, target){
  var hash = {};                                         // 1
  
  for (var i=0; i < arr.length; i++){                    // 1
    hash[arr[i]] = i;                                    // n
  }
  
  for (var i=0; i < arr.length; i++){                    // 1
    var value = arr[i];                                  // n
    var diff = target - value;                           // n
    
    var match = hash[diff];                              // n * 1   (hash[] = constant)
    
    if (match && match != i){                            // n
      return true;
    }
    
  }
  
  return false;                                          // 1
}

// 1 + 1 + n + 1 + n + n + n + n + 1
// 5 + 5 * n
// O(5n + 5) ~= O(5n) ~= O(n)

console.log(targetSums([1,2,3,4,5,6], 3));
console.log(targetSumsV2([1,2,3,4,5,6], 3));
console.log([1,2,3,4,5].indexOf(5))