The Two Sum Problem in JavaScript

Introduction

The Two Sum problem is a classic coding problem that asks you to find two numbers in an array that add up to a specific target sum. It tests your ability to search for and manipulate data efficiently. In this article, we will explore a detailed solution to the Two Sum problem using JavaScript.

Problem Statement

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

Approach: Using a Hash Map

To solve the Two Sum problem efficiently, we can use a hash map to store the difference between the target sum and the current element as we iterate through the array. Here’s how the solution works:

1. Create an empty hash map to store the difference between the target sum and the current element, along with their indices.
2. Iterate through the array, and for each element:
   • Calculate the difference diff between the target sum and the current element.
   • Check if diff exists in the hash map.
     • If it does, return the indices of the current element and the corresponding value from the hash map.
     • If it doesn’t, add the current element and its index to the hash map.
3. If no solution is found, return an empty array.

JavaScript Code

Here’s the JavaScript code that implements the solution:

const twoSum = (nums, target) => {
  const map = new Map();

  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    
    if (map.has(diff)) {
      return [map.get(diff), i];
    }
    
    map.set(nums[i], i);
  }

  return [];
};

// Example usage
const nums = [2, 7, 11, 15];
const target = 9;
const result = twoSum(nums, target);
console.log(result); // Output: [0, 1]

In this example, we define the twoSum function that takes an array of numbers (nums) and a target sum (target) as parameters. We create a new Map object called map to store the difference between the target sum and the current element, along with their indices.

We iterate through the nums array using a for loop. For each element, we calculate the difference (diff) between the target sum and the current element. We then check if the map contains the diff as a key. If it does, we retrieve the index of the difference from the map along with the current index, and return them as an array. If it doesn’t, we add the current element and its index to the map.

If no solution is found after iterating through the entire array, we return an empty array.

Time and Space Complexity Analysis

Let’s analyze the time and space complexity of the solution to the Two Sum problem.

Time Complexity

The time complexity of the solution is O(n), where n is the length of the input array nums.

The for loop iterates through each element of the array once, resulting in a linear time complexity. The hash map operations, such as map.has() and map.get(), have an average time complexity of O(1). Therefore, the overall time complexity is dominated by the linear iteration through the array.

Space Complexity

The space complexity of the solution is O(n), where n is the length of the input array nums.

We use a hash map to store the difference between the target sum and the current element, along with their indices. In the worst case scenario, where there is no solution and we iterate through the entire array, the hash map may store all the elements of the array. Thus, the space complexity is linearly proportional to the size of the input array.

Handling Edge Cases

When implementing the solution to the Two Sum problem, it’s important to consider various edge cases to ensure the correctness and robustness of the code. Let’s explore a few common edge cases and how to handle them.

Edge Case 1: Empty Array

If the input array nums is empty, there are no elements to check for the sum, and there can be no valid solution. In this case, you can return an empty array to indicate that no solution exists.

const twoSum = (nums, target) => {
  if (nums.length === 0) {
    return [];
  }
  
  // Rest of the code
};

Edge Case 2: No Solution

There may be scenarios where there is no valid solution in the input array. In this case, the loop will iterate through all the elements without finding a match in the hash map. To handle this, you can return an empty array after the loop to indicate that no solution was found.

const twoSum = (nums, target) => {
  // Rest of the code

  return []; // No solution found
};

Edge Case 3: Duplicate Elements

If the input array contains duplicate elements and the target sum can be achieved by using the same element twice, you need to ensure that the returned indices are different. To handle this, you can modify the code slightly by checking if the index from the hash map is different from the current index.

const twoSum = (nums, target) => {
  const map = new Map();

  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    
    if (map.has(diff) && map.get(diff) !== i) {
      return [map.get(diff), i];
    }
    
    map.set(nums[i], i);
  }

  return [];
};

With this modification, if a duplicate element can be used to achieve the target sum, the indices returned will be different.

Conclusion

Considering and handling edge cases is crucial to ensure the correctness and robustness of your code. By addressing scenarios such as empty arrays, no solution found, or duplicate elements, you can provide more accurate and reliable solutions. Always test your code with various edge cases to ensure its correctness and handle any potential issues effectively.