In this tutorial, we will walk through solving the Two Sum problem using JavaScript. The Two Sum problem is a common interview question that requires you to find two numbers in an array that add up to a given target. We'll cover the problem description, explain the step-by-step process for solving it, and provide multiple approaches along with code examples.

By the end of this post, you'll know how to implement the Two Sum solution efficiently using JavaScript, including tips on best practices.

Problem Statement

Given an array of integers, return the indices of the two numbers that add up to a specific target.

Example:

Input: nums = [2, 7, 11, 15], target = 9  
Output: [0, 1]  
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Assumptions:

  • Each input will have exactly one solution.
  • You may not use the same element twice.
  • You can return the answer in any order.

Approach 1: Brute Force

The simplest approach to solve this problem is to use a brute force method. Here, we check all pairs of numbers in the array and see if their sum equals the target.

Steps:

  1. Use two nested loops to go through every pair of numbers in the array.
  2. For each pair, check if their sum is equal to the target.
  3. If it is, return their indices.

Code Implementation:

function twoSum(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];
            }
        }
    }
    return [];
}

Explanation:

  • The outer loop picks the first number, and the inner loop picks the second number.
  • If the sum of the two numbers matches the target, their indices are returned.

Time Complexity:

  • Time Complexity: O(n²) – This solution requires checking every pair of numbers, making it quadratic in time.
  • Space Complexity: O(1) – No additional space is used except for storing the result.

Approach 2: Using a HashMap (More Efficient)

The brute force approach works but is not efficient for large arrays. A more efficient solution uses a HashMap (or JavaScript’s Map) to store numbers and their indices as we iterate through the array. This allows us to find the complement of a number in constant time.

Steps:

  1. Initialize an empty HashMap.
  2. Iterate over the array, and for each number, calculate its complement (target - current_number).
  3. Check if the complement is already in the HashMap:
    • If yes, return the index of the complement and the current index.
    • If no, store the current number and its index in the HashMap.

Code Implementation:

function twoSum(nums, target) {
    let map = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i];
        
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        
        map.set(nums[i], i);
    }
    
    return [];
}

Explanation:

  • We create a Map to store the numbers we encounter, along with their indices.
  • For each number in the array, we calculate its complement (target - nums[i]).
  • If the complement exists in the Map, we return its index and the current index.
  • If it doesn’t exist, we add the current number and its index to the Map for future lookups.

Time Complexity:

  • Time Complexity: O(n) – We only loop through the array once, making this a linear-time solution.
  • Space Complexity: O(n) – We store up to n numbers in the Map.

Edge Cases

While the problem guarantees exactly one solution, you should still account for various edge cases during implementation:

  1. Negative and Positive Numbers:
    The array may contain both negative and positive numbers. Ensure that the solution works for both.

    const nums = [-3, 4, 3, 90];
const target = 0;
const result = twoSum(nums, target);
console.log(result);  // Output: [0, 2]

  2. Duplicate Values:
    The array may contain duplicate values, and the solution should still return the correct indices.

    const nums = [3, 3];
const target = 6;
const result = twoSum(nums, target);
console.log(result);  // Output: [0, 1]

  3. Array with Only Two Elements:
    Since the problem guarantees at least two elements, the array can have exactly two elements, and the solution should still work.

    const nums = [1, 4];
const target = 5;
const result = twoSum(nums, target);
console.log(result);  // Output: [0, 1]

  4. Zeros in the Array:
    If the array contains zeros, the solution should correctly handle the target involving zero.

    const nums = [0, 4, 3, 0];
const target = 0;
const result = twoSum(nums, target);
console.log(result);  // Output: [0, 3]

  5. Large Inputs:
    If the array contains a large number of elements, the hash map approach ensures efficiency even with significant data size.

    const nums = Array.from({ length: 100000 }, (_, i) => i);
const target = 199999;
const result = twoSum(nums, target);
console.log(result);  // Output: [99998, 99999]

Best Practices

Here are some best practices to consider when solving the Two Sum problem or similar problems:

  • Use a HashMap for efficiency: While the brute force approach may seem straightforward, it’s inefficient for large datasets. The HashMap approach provides a time complexity of O(n) and is much more scalable.
  • Consider edge cases: Always think about edge cases like empty arrays, arrays with only one element, or cases where no solution exists.
  • Optimize for readability: The HashMap approach is not only efficient but also makes the code more readable and easier to understand.
  • Don’t forget to return an empty array when no solution is found: In some cases, it’s important to return an appropriate value (such as an empty array) if no valid indices are found.

Conclusion

The Two Sum problem is a great example of how we can solve algorithmic challenges using different approaches in JavaScript. We started with a brute force solution that checks every pair of numbers and moved on to a more efficient approach using a HashMap to achieve linear time complexity.

By understanding and implementing these two approaches, you can tackle this problem efficiently and also apply similar techniques to other problems like Three Sum or Four Sum.