Day 5 - Challenge 1 - Two Sum

Solving the Two Sum Problem in JavaScript

The Two Sum problem is a classic coding challenge that involves finding two numbers in an array that add up to a given target sum. In this blog post, we'll walk through the problem-solving process step by step and implement a solution in JavaScript.

Problem Statement

Given an array of integers and a target sum, our task is to find two distinct numbers from the array that add up to the target sum. We need to return the indices of these two numbers in the array.

For example, if the input array is [2, 7, 11, 15] and the target sum is 9, the output should be [0, 1] because 2 + 7 = 9.

Approach

To solve this problem efficiently, we can use a hash map to store the numbers we have encountered so far along with their indices. As we iterate through the array, we can check if the difference between the current number and the target sum exists in the hash map. If it does, then we've found our solution.

Here's the step-by-step approach:

1. Create an empty hash map to store numbers and their indices.
2. Iterate through the array.
3. For each number num at index i, calculate the complement as target - num.
4. Check if the complement exists in the hash map.
   • If it does, return the indices [hashMap[complement], i].
   • If not, add the current number and its index to the hash map.

Implementation

Let's implement the solution in JavaScript:

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

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const complement = target - num;

        if (hashMap.hasOwnProperty(complement)) {
            return [hashMap[complement], i];
        }

        hashMap[num] = i;
    }

    return null; // If no solution is found
}

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

Demo

Two Sum Problem Solver

Conclusion

The Two Sum problem is a common coding challenge that tests your problem-solving skills and knowledge of hash maps. By using a hash map to keep track of encountered numbers and their indices, we can efficiently solve this problem in linear time complexity.

Remember to analyze the time and space complexity of your solution. In this case, the time complexity is O(n), where n is the number of elements in the array, and the space complexity is O(n) as well due to the hash map.

I hope this blog post helps you understand how to approach and solve the Two Sum problem using JavaScript. Happy coding!

Now write the same program in your favorite language in comment section. 

Other Challenges:

1. Day 2 Challenges
2. Day 3 Challenges
3. Day 4 Challenges