How to Solve Two Sum Problem with JavaScript

The Two Sum problem is a classic coding interview question that often tests a candidate's problem-solving and algorithmic skills.

Given an array of integers and a target sum, the task is to find two distinct indices that add up to the target sum.

In this article, we'll explore how to solve the Two Sum problem using JavaScript.

Brute Force Approach

The simplest way to approach the Two Sum problem is by using a brute force approach, which involves checking every possible pair of numbers in the array to see if their sum equals the target. Here's how you could implement this approach in JavaScript

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

While this approach is straightforward, it has a time complexity of O(n^2), where n is the number of elements in the input array. This is not very efficient, especially for larger arrays.

Using a Hash Map

A more efficient solution involves using a hash map (also known as an object in JavaScript). The idea is to store each element of the array in the map along with its index.

As we iterate through the array, we check if the difference between the target and the current element exists in the map. If it does, we've found the pair that adds up to the target. This approach has a time complexity of O(n) because we iterate through the array once, and each hash map lookup is O(1).

Here's the implementation:

function twoSum(nums, target) {
    const numToIndex = {};

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (complement in numToIndex) {
            return [numToIndex[complement], i];
        }
        numToIndex[nums[i]] = i;
    }
    
    return [];
}

Example Usage

Let's consider an example to demonstrate how the twoSum function works:

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

In this example, the elements at indices 0 and 1 (2 and 7) add up to the target value of 9.

Conclusion

When first attemped to the question to solve Solving the Two Sum problem efficiently requires more than just brute force. By using a hash map to keep track of elements and their indices, we can achieve a linear time complexity solution. This is particularly useful when dealing with larger arrays where the brute force approach becomes impractical

Keep in mind that understanding and implementing such algorithms is not only valuable for coding interviews but also for building efficient solutions in real-world programming scenarios.

Thank you for reading.