1. Two Sum

Naive Solution

Compare every number in the array.

  • Time Complexity: O(n^2), because we would have to traverse the array two times.

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const map = {};
    
    for (let i = 0; i < nums.length; i++) {
        const diff = target - nums[i];
        if (map[diff] !== undefined) {
            return [map[diff], i];
        }
        map[nums[i]] = i;
    }
};

Complexity

  • Time Complexity: O(N), where N is the size of nums.
  • Space Complexity: O(N), where N is the size of map.

All Solutions