Two Sum

Problem Statement

Given an array of integers nums and an integer target, return the 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.

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

Approach: One-Pass Hash Map

The brute force approach uses nested loops to check every pair, which takes $O(n^2)$ time. The optimal approach uses a Hash Map to reduce the time complexity to $O(n)$.

As we iterate through the array, we can check if the complement of the current number (i.e., target - current_number) already exists in our Hash Map.

1. Initialize an empty Hash Map map to store numbers as keys and their indices as values.
2. Iterate through the array nums using a standard for loop so you have access to the index i.
3. For each number, calculate its complement = target - nums[i].
4. Check if the complement exists in the map.
   • If it does, you’ve found the pair! Return an array containing the map[complement] (the stored index) and i (the current index).
   • If it does not, add the current number and its index to the map as a key-value pair (map[nums[i]] = i) so it can be found by subsequent numbers.

Solution

function twoSum(nums, target) {
    const map = {};
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        if (complement in map) {
            return [map[complement], i];
        }
        
        map[nums[i]] = i;
    }
    
    return []; // Should not be reached based on problem constraints
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the length of the array. We iterate through the array exactly once. Hash map lookups and insertions take $O(1)$ time on average.
• Space Complexity: $O(n)$. In the worst-case scenario, we might need to store almost all $n$ elements in the hash map before finding a match.