Two Sum Problem: Exploring Naive and Efficient Solutions in JavaScript

The Two Sum problem is a classic coding challenge that frequently arises in various coding interviews and competitive programming scenarios. Given an array of integers and a target value, the task is to find two numbers in the array that add up to the target. In this blog post, we’ll explore two different approaches to tackle this problem: the naive approach and a more efficient one.

The Problem Statement

Let’s define the problem first. Given an array of numbers nums and an integer target, you need to return an array containing the indices of the two numbers such that they add up to the target.

Example:

const nums = [2, 7, 11, 15];
const target = 9;

// The solution should return [0, 1] because nums[0] + nums[1] equals the target.

Naive Approach

The naive approach to solving the Two Sum problem is to use nested loops to compare each element with every other element in the array. Here’s a JavaScript function to illustrate this approach:

const naiveTwoSum = (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];
      }
    }
  }
};

While this approach works and provides the correct solution, it has a time complexity of O(n^2), where ‘n’ is the number of elements in the array. This means that for larger arrays, the time it takes to find the solution increases significantly.

Efficient Approach

const efficientTwoSum = (nums, target) => {
  let numIndex = new Map();

  for (let i = 0; i < nums.length; i++) {
    let targetValue = target - nums[i];

    if (numIndex.has(targetValue)) {
      return [numIndex.get(targetValue), i];
    }

    numIndex.set(nums[i], i);
  }
};

In this approach, we maintain a Map called numIndex. We iterate through the array, calculating the difference between the target value and the current element (i.e., targetValue = target - nums[i]). We then check if this targetValue exists in our numIndex Map. If it does, we have found the pair of numbers that adds up to the target.

The efficient approach has a time complexity of O(n), where ‘n’ is the number of elements in the array. It is more optimal and performs significantly better for larger arrays.

Wrapping Up

In this blog post, we explored two different approaches to solving the Two Sum problem in JavaScript: the naive approach with a time complexity of O(n^2) and the efficient approach with a time complexity of O(n). The efficient approach, which uses a HashMap, is the recommended method for solving this problem, especially for larger datasets.