1
\$\begingroup\$

I was for the first time doing a challenge on the leetcode, and I have come up with the JS code for finding the indexes of 2 numbers that add up to a target value that looks like this:

let nums = [-3, 0, 3, 2, 4, 0]; 
let target = 0;

var twoSum = function(nums, target) {
    let checkedNums = [];
    let result = [];
    nums.forEach((num, i) => {
        if (result.length === 0) {
            if (checkedNums.includes(target - num)) {
                result = [nums.indexOf(target - num), i];
            } else {
                    checkedNums.push(num);
            }
        }
    })
    return result;
};

twoSum(mums, target) // outputs [0, 2]

But, when I saw that the runtime of this code it 72ms, and that there are far better runtimes I wonder how can I optimise this code to get a better runtime? Here is the fiddle. I have also came up with solution, which I thought would be faster since we stop the for loop immediately when the solution is found, but I didn't see any decrease in the runtime:

var twoSum = function(nums, target) {
    let checkedNums = [];
    for (let i = 0; i < nums.length; i++) {
        if (checkedNums.includes(target - nums[i])) {
          return [nums.indexOf(target - nums[i]), i];
        } else {
          checkedNums.push(nums[i]);
        }
    }
};
\$\endgroup\$
  • \$\begingroup\$ Is the nums array consistent with the rules at the description at linked document? \$\endgroup\$ – guest271314 Nov 26 '17 at 2:07
  • \$\begingroup\$ yes, the nums array is one of the examples I have got as a test array \$\endgroup\$ – Leff Nov 26 '17 at 2:20
  • \$\begingroup\$ Your main problem is performing repeated array searches via checkedNums.includes within the inner loop (linear time). Use a Map instead. Looking up elements within a Map is much faster (constant time on average). You can also get rid of the final nums.indexOf by storing checked numbers together with their indices - as a mapping number -> index. \$\endgroup\$ – le_m Nov 26 '17 at 2:22
  • \$\begingroup\$ @Leff "You may assume that each input would have exactly one solution" Value of index 1 added to value of index 5 at nums array at code at Question is equal to target, yes? \$\endgroup\$ – guest271314 Nov 26 '17 at 2:22
2
\$\begingroup\$

Style

Your code is pretty readable already. But you mix var and let. I prefer consistent style.

Also, you use a function expression instead of a function declaration - there are subtle differences, but it's mostly a matter of personal preference. To me, the function declaration seems simpler.

Runtime complexity

Your main issue is performing full array searches via checkedNums.includes (in linear time) within the inner loop. By using an alternative data structure such as a simple object {}, a Set or a Map which complete such lookups much faster (in constant time), your performance will improve drastically for large inputs.

You can also get rid of the final nums.indexOf by mapping numbers to their indices. This doesn't improve theoretical runtime complexity, but still improves performance. The same holds for breaking out of the loop early as soon as a solution is found.

Implementation

// Return indices of first two number summing up to target:
function twoSums(numbers, target) {
  const map = new Map();
  for (let i = 0; i < numbers.length; ++i) {
   if (map.has(target - numbers[i])) {
      return [map.get(target - numbers[i]), i];
    } else {
      map.set(numbers[i], i);
    }
  }
}

// Example:
console.log(twoSums([-3, 0, 3, 2, 4, 0], 0)); // [0, 2]

Benchmark

Measuring average runtime over 1000 runs for input arrays of different length, we get the following results:

length  original [ms]  improved [ms]
   100            2.4            7.2
   500           32.8           37.6
  1000          120.6           71.2
  5000         2703.4          401.2
 10000        11132.5          792.5
 50000       265770.5         3633.5
100000      1052582.0         7776.5

While the original implementation performs better for very small inputs, the improved implementation performs much better for longer arrays. This confirms our above runtime complexity analysis.

Plotting the times against the input length clearly shows the quadratic nature of the original runtime complexity vs. the linear runtime complexity of the improved implementation:

runtime complexity comparison

\$\endgroup\$
  • \$\begingroup\$ This is the best solution. Great formatting and you came with the idea of the map. \$\endgroup\$ – Pavlo Nov 26 '17 at 3:38
  • \$\begingroup\$ I did a benchmark on this and you are running 10 times slower than the OPs original post, that would be 720ms in comparison going by the OP's time of 72ms \$\endgroup\$ – Blindman67 Nov 26 '17 at 7:29
  • \$\begingroup\$ @Blindman67 I added my benchmark results. \$\endgroup\$ – le_m Nov 26 '17 at 23:09
  • \$\begingroup\$ @le_m you also changed the code to use Map rather than use an object as a map which makes all the difference, nice. V8 (if you are using it) has recently added significant performance improvements to Map and Set making them indispensable as lookups. \$\endgroup\$ – Blindman67 Nov 26 '17 at 23:36
  • \$\begingroup\$ @Blindman67 I just ran the benchmark on Firefox / Ubuntu again with a plain object instead of Map, and the plain object is indeed much slower here, too. It is still faster than OP's code for large arrays, though. \$\endgroup\$ – le_m Nov 27 '17 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.