Solving the LeetCode Two Sum Problem Using JavaScript

The Two Sum problem is a classic coding challenge that involves finding two distinct indices in an array whose elements sum up to a given target value. It is similar to the 3Sum Problem, although requires different techniques to solve. Here, we will explore how to efficiently solve the Two Sum problem using JavaScript.

The Problem

Given an array of integers and a target value, our goal is to find two distinct indices (i and j) such that the sum of the elements at those indices is equal to the target value. The function should return an array containing the two indices (i and j).

The signature of our solution will look something like this:

const twoSum = (nums: number[], target: number): number[] | undefined => {
  // Implementation goes here
};

It's important to bear in mind that with this problem, you should assume that each input would have exactly one solution, and you cannot use the same element twice.

Solution Using a Hash Map

This problem is an ideal candidate for using a hash map (object in JavaScript) to keep track of the elements we have encountered so far whilst working out the solution.

The idea is to iterate through the array, and for each element, check if its complementary value (target minus the current element) is already in the hash map. If it is, we have found the two elements that sum up to the target.

This approach allows us to achieve a time complexity of O(n) as we can perform lookups in constant time.

The solution looks something like this:

const twoSum = (nums: number[], target: number): number[] | undefined => {
  // Create an empty hash map to store elements and their indices.
  const elementIndexMap: { [key: number]: number } = {};

  // Iterate through the array, checking for the complementary element in the hash map.
  for (let i = 0; i < nums.length; i++) {
    const currentElement = nums[i];
    const complement = target - currentElement;

    if (elementIndexMap[complement] !== undefined) {
      // Found a pair that sums up to the target
      return [elementIndexMap[complement], i];
    }

    // Save the current element and its index in the hash map
    elementIndexMap[currentElement] = i;
  }

  // No valid pair found
  return undefined;
};

Using this function, we would see results like this:

console.log(twoSum([2, 7, 11, 15], 9));  //=> [0, 1] (nums[0] + nums[1] = 2 + 7 = 9)
console.log(twoSum([3, 2, 4], 6));  //=> [1, 2] (nums[1] + nums[2] = 2 + 4 = 6)
console.log(twoSum([3, 3], 6));  //=> [0, 1] (nums[0] + nums[1] = 3 + 3 = 6)
console.log(twoSum([1, 2, 3, 4, 5], 9));  //=> [3, 4] (nums[3] + nums[4] = 4 + 5 = 9)

Using the Two‑Pointer Method

There is another solution you could also consider using the Two Pointers Technique instead of hash maps. The idea behind the Two Pointers approach is to have two pointers, one starting from the beginning of the array (left pointer) and the other starting from the end (right pointer). We then compare the sum of the elements at these two pointers with the target value.

Here's how the Two Pointers approach would work:

1. Sort a copy of the input array in ascending order.
2. Initialise two pointers: one at the beginning (left) and the other at the end (right) of the sorted array.
3. Calculate the sum of the elements at the left and right pointers.
4. If the sum is equal to the target, find and return the two values' indices in the original array, using distinct positions when the values are equal.
5. If the sum is less than the target, move the left pointer to the right to increase the sum.
6. If the sum is greater than the target, move the right pointer to the left to decrease the sum.
7. Repeat steps 3 to 6 until we find the target sum or the left pointer crosses the right pointer.

Here's how it might look in code:

const twoSumTwoPointers = (
  nums: number[],
  target: number
): number[] | undefined => {
  // Create a copy of the input array and sort it in ascending order
  const sortedNums = [...nums].sort((a, b) => a - b);

  let left = 0;
  let right = sortedNums.length - 1;

  while (left < right) {
    const sum = sortedNums[left] + sortedNums[right];

    if (sum === target) {
      // Found a pair that sums up to the target
      const leftIndex = nums.indexOf(sortedNums[left]);
      const rightIndex = nums.lastIndexOf(sortedNums[right]);
      return [leftIndex, rightIndex];
    } else if (sum < target) {
      // Move the left pointer to increase the sum
      left++;
    } else {
      // Move the right pointer to decrease the sum
      right--;
    }
  }

  // No valid pair found, return undefined
  return undefined;
};

And using the function we can expect:

console.log(twoSumTwoPointers([2, 7, 11, 15], 9));  //=> [0, 1] (nums[0] + nums[1] = 2 + 7 = 9)
console.log(twoSumTwoPointers([3, 2, 4], 6));  //=> [1, 2] (nums[1] + nums[2] = 2 + 4 = 6)
console.log(twoSumTwoPointers([3, 3], 6));  //=> [0, 1] (nums[0] + nums[1] = 3 + 3 = 6)
console.log(twoSumTwoPointers([1, 2, 3, 4, 5], 9));  //=> [3, 4] (nums[3] + nums[4] = 4 + 5 = 9)

This is generally the less preferred solution in this problem simply because it requires that the array is sorted so it takes longer; it has a time complexity of O(n log n) due to the sorting step. However, once the array is sorted, the actual two‑pointer traversal has a time complexity of O(n), very similar to the hash maps method.

Wrapping Up

Of the two solutions to the Two Sum problems, the best approach will depend on the specific characteristics of the input data.

For unsorted input, I would usually start with the hash map approach. Assuming average constant‑time lookups, it takes linear time and avoids the sorting step.

The two‑pointer traversal is useful when data is already sorted. In the implementation above, though, [...nums] creates a separate array before sorting. That copy takes O(n) extra space, so this version does not save memory compared with the hash map. A traversal over an already‑sorted array can use constant extra space, but that is a different starting point from the copied‑array solution shown here.

Ultimately, the best approach will vary based on the specific requirements of the problem and the characteristics of the input data. In an interview scenario, I am sure either approach would be very suitable ‑ especially if you can then explain how it works and what the alternative solution might look like.