Understanding Hashmaps with Javascript

Question

I need help understanding what and how to use hash maps in javascript. I have an example where Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Can someone breakdown what this hashmap solution is doing and why it's better? Also if someone would be kind of enough to give me a similar problem to practice with that would extremely helpful.

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

My BruteForce Solution

for (var i = 0; i < nums.length; i++) {
        for (var j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                result.push(i);
                result.push(j);
            }
        }
    }
    return result;
}
console.log(twoSum([2, 7, 11, 15], 9));

HashMapSolution

function twoSumBest(array, target) {
    const numsMap = new Map();
    for (let i = 0; i < array.length; i++) {
        if(numsMap.has(target - array[i])) {
            return [numsMap.get(target - array[i], i)];
            // get() returns a specified element associated with the specified key from the Map object.
        } else {
            numsMap.set(array[i], i);
            //  set() adds or updates an element with a specified key and value to a Map object.
        }
    }
}

@JonasWilms if OP does not not how HashTable/HashMap work... assuming knowledge of O-notation is a stretch... Also number of loops indeed is not an indication of complexity. If Map.has would use just linear search the fact there is only one outer loop will not change overall complexity - you comment could lead to spreading common idea that function calls are always O(1). — Alexei Levenkov
– Alexei Levenkov, Commented Jan 24, 2020 at 18:56

Jonas Wilms · Accepted Answer · 2020-01-24 19:13:09Z

If you want to reach 10 and you have 7, you already know that the other number that is needed is 3. So for every number in the array, you only have to check wether the complementary number is in the array, you don't necessarily have to search for it.

If we go over all array entries once (let's call them a) and add them to a hashmap with their index, we can go over the array again and for each entry (b), we can check if the hashmap contains an a (where a + b = target). If that entry is found, the index of b is known, and the index of a can be retrieved from the hashmap¹. Now using that method we only iterate the array twice (or just once, doesn't matter that much), so if you have 1000 numbers, it'll iterate 1000 times. Your solution will iterate 1000 * 1000 times (worst case). So the hashtable approach is way faster (for larger arrays).

¹ Hashmaps are very special, as the time it takes to look up a key takes a constant amount of time, so it does not matter wether the array has 10 or 10 million entries (the time complexity is constant = O(1)). Thus, looking up in an hashtable is way better than searching inside of an array (which takes more time with more entries = O(n)).

Collectives™ on Stack Overflow

Understanding Hashmaps with Javascript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related