General Idea

The Two Sum problem is a classic algorithmic problem. It asks you to find two numbers in an array that add up to a specific *target * that is provided and then return their indices from the given array.

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target. Each input will have exactly one solution, and you may not use the same element twice.

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] nums[1] = 2 7 = 9

Approach 1 Brute force

First approach to any problem could just be to get something done and the easiest thing conceptually.

Iterate through the array with two loops and check all pairs of numbers.

const twoSum = (nums, target) => {
  for(let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      console.log(` i is ${nums[i]} and k is ${nums[j]}`)
      // lets check if we add the 2 numbers if it equals target
      if (target === nums[i] + nums[j]) {
        return [i, j]
      }
    }
  }
};

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));

Approach 1 Complexity

Time Complexity is O(n2)

1. Nested loops checking every pair of numbers
2. Checks every possible combination
3. Becomes very slow with large arrays

Space Complexity is O(1)
1.We have created no new data structure

Approach 2 More Efficient and what we want.

We will use a hash map to solve this. Let's explain this algorithm a bit

1. We use a hash map (object in JavaScript) to store numbers we've seen
2. For each number, we calculate its complement (target - current number)
3. We check if the complement exists in our map
4. If it does, we've found our two numbers and return their indices
5. If not, we add the current number to the map

So first solution could be using the regular JS object and building our HashMap that way

const twoSumOptimizedRegularObject = (nums, target) => {
  const objectStuff = {}

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i] 

    if (complement in objectStuff) {
      return [objectStuff[complement],i]
    }
    objectStuff[nums[i]] = i 
  }
}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimizedRegularObject(nums, target));

The second solution is actually using the Map Data Structure in JS.This allows for a more stricter and more robust implementations, using a Map object (introduced in ES6) and is often preferred. A Map provides explicit hash map behavior and avoids some quirks of JavaScript objects, like inheriting properties from Object.prototype.

const twoSumOptimized = (nums, target) => {
  const mapOfStuff = new Map()

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i]

    if (mapOfStuff.has(complement)) {
      return [mapOfStuff.get(complement), i]
    }
    mapOfStuff.set(nums[i], i)
  }

}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimized(nums, target));

Approach 2 Complexity

Time Complexity is O(n)

1. Single pass through the array
2. Hash map provides O(1) lookup
3. Total time scales linearly with array size

Space Complexity is O(n)
In worst case, we might store nearly all numbers
Trade-off between time and memory efficiency

Caveats

1. Empty array
2. No solution exists
3. Multiple solution are possible. In this case, ask if you return after the first iteration.

The above is the detailed content of Two Sum problem in Javascript. For more information, please follow other related articles on the PHP Chinese website!