Optimizing the Two Sum Problem with HashMap in JavaScript

I recently tackled a classic interview problem, given an array of numbers and a target value, find the indices of the two numbers that add up to the target. This problem, known as “Two Sum,” might seem straightforward, but the key is finding the most efficient solution.

Input: nums = [2, 5, 3, 11], target = 7
Output: [0, 1]

Initial Approach: Brute Force

When I first encountered this problem, my immediate solution was to use a nested loop to check all possible pairs.

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

To improve efficiency, I turned to the Map object in JavaScript, which allows us to reduce the time complexity to O(n). But what exactly is a Map?

Map in JavaScript: Similar to HashMap in Other Languages

In JavaScript, the Map object functions similarly to a HashMap in other programming languages like Java. Both Map and HashMap are data structures that store key-value pairs, enabling fast lookups, insertions, and deletions.

An example for Map:

let personMap = new Map();
personMap.set("name", "Anne");
personMap.set("age", 23);

console.log(personMap.get("name")); // Outputs: Anne
personMap.set("age", 24); // Updates the age to 24

A key difference is that JavaScript’s Map allows for any type of key (including objects and functions), maintains the order of its elements, and provides methods specifically designed for handling key-value pairs. This makes it a more robust option compared to plain JavaScript objects.

Implementing the Solution:

Here’s how we can use a Map to implement the optimized Two Sum solution:

function twoSum(nums, target) {
    let map = new Map();  // Creating an empty Map
    
    for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i];
        if (map.has(complement)) {
            return [i, map.get(complement)];
        }
        map.set(nums[i], i);  // Store the index of the current element
    }
    
    throw new Error("No solution found");
}

This approach ensures that we only pass through the array once, making it much more efficient.

By using a Map, we’ve optimized the Two Sum problem to run in linear time, making it a go-to solution during coding interviews. Keep this technique in your back pocket for similar problems where efficiency is key!