Created
December 23, 2014 18:06
-
-
Save mark-adams/8f33d78fcf0293ab77ee to your computer and use it in GitHub Desktop.
Target Sums: A great interview programming problem with O(n^2) and O(n) solutions
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * 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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment