Two Sum Problem

Problem Description

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 would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Difficulty Level: Easy

LeetCode Problem #1: Link

Approach 1: Brute Force Algorithm
Time Complexity: O(n^2)
Solution:

var twoSum = function(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: Hashing & Two-pointer Technique
Time Complexity: O(n)
Solution:

var twoSum = function(nums, target) {
    const indexMap = new Map();

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

        if (indexMap.has(complement)) {
            return [indexMap.get(complement), i];
        }

        indexMap.set(nums[i], i);
    }

    return []; 
};

Algorithm Explanation:

Initialize an empty Map called indexMap. This map will store each number encountered in the array as a key and its index as the corresponding value.

Iterate through the input array nums using a for loop. For each element at index i, do the following:

Calculate the complement by subtracting the current element (nums[i]) from the target. The complement is the value that, when added to nums[i], results in the target sum.

Check if the map indexMap contains the calculated complement as a key. This is done using the .has(complement) method of the Map. If the complement exists in the map, it means that a pair of numbers has been found whose sum equals the target.

In this case, return an array containing the indices of the two numbers. The first index is retrieved from the map using indexMap.get(complement) (since the map stores indices as values), and the second index is simply i.
If the complement is not found in the map, it means that a matching pair has not been encountered yet. In this case, add the current number (nums[i]) to the map with its index as the value. This prepares the map for future lookups as the algorithm progresses through the array.

If the loop completes without finding a valid pair that sums up to the target, return an empty array to indicate that no solution was found.

Time Complexity:
The algorithm performs a single pass through the array, performing constant-time operations (hash map lookups and inserts) at each step. Therefore, the time complexity is O(n), where n is the length of the input array.

Example:

References:

• LeetCODE
• Grind 75
• mdn web docs more about (.set, .get, .has)