Two Sum Problem in Javascript

Given an array of integers nums and an integer target, your task is to identify the indices of two distinct numbers in the array that sum up to the specified target.

Each input will have exactly one solution, and you cannot use the same element more than once. Return the answer in any order.

Examples

// Example 1:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] // Because nums[0] + nums[1] = 2 + 7 = 9

// Example 2:
Input: nums = [3, 2, 4], target = 6
Output: [1, 2] // Because nums[1] + nums[2] = 2 + 4 = 6
 

Solution

There can be two approaches to solve this problem:

1. Brute Force approach
2. Optimized approach using Hashing

Approach 1: Brute Force

This brute force method checks every possible pair of numbers in the array to see if they add up to the target. While it’s simple, it can be slow for larger arrays. The time complexity is O(n²), which isn’t efficient for big datasets.

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

Approach 2: Optimized Using Hashing

This optimized solution uses a hash map to store numbers we’ve already seen along with their indices. By calculating the difference needed to reach the target, we can quickly check if that number is already in our map. The formula we use is: difference = target - nums[i].

If this difference is present in our hash map, we‘ve found our answer! This approach reduces the number of checks we need to do, resulting in a much faster O(n) time complexity, which is perfect for larger datasets.

function twoSumOptimized(nums, target) {
    const numMap = new Map();

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

    return [];
}