DEV Community

Masaki Fukunishi
Masaki Fukunishi

Posted on • Updated on

LeetCode #1 Two Sum with JavaScript

Solutions to LeetCode's 1. Two Sum with JavaScript.

Solution 2 also addresses the following follow-up.
Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?

An easy one to come up with is a nested for loop.

Solution 1: Nested for loop

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
};
Enter fullscreen mode Exit fullscreen mode
  • Time complexity: O(n^2)
  • Space complexity: O(1)

This solution has O(n^2) time complexity because of nesting loops, so I want to find another way.

Solution 2:Using object

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
  const hash = {};
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (hash[complement] !== undefined) {
      return [i, hash[complement]];
    }
    hash[nums[i]] = i;
  }
};
Enter fullscreen mode Exit fullscreen mode
  • Time complexity: O(n)
  • Space complexity: O(n)

Store the nums value in the keys of the hash and the index in the value.

hash[nums[i]] = i;
Enter fullscreen mode Exit fullscreen mode

Then, in each loop, check whether the target minus the nums value exists in the hash.
If it exists, it returns the index of the current loop and the value of the matching hash (index of the stored nums).

const complement = target - nums[i];
if (hash[complement] !== undefined) {
  return [i, hash[complement]];
}
Enter fullscreen mode Exit fullscreen mode

In many cases, we want to avoid Time complexity: O(n^2), so I think solution 2 using hash is better.

Top comments (0)