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], 10));  //=> [3, 4] (nums[3] + nums[4] = 4 + 5 = 10)

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 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, return the indices of the elements at the left and right pointers.
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], 10));  //=> [3, 4] (nums[3] + nums[4] = 4 + 5 = 10)

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.

Generally, if the array is unsorted, then the Hash Map approach is the preferred choice due to its guaranteed linear time complexity. It is simple to implement and requires less code.

On the other hand, if the input array is already sorted or can be sorted efficiently without affecting the original data, then the Two Pointers approach may be a better choice. Whilst the time complexity for the Two Pointers approach is higher due to sorting, it can still be efficient in practice for moderately sized arrays, and it saves memory by not requiring a separate hash map.

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.