How Maps Improve Efficiency of Algorithm

Maps are data structures that facilitate the quick search, insertion, and deletion of key-value pairs. They are sometimes referred to as dictionaries, hash tables, or associative arrays. Maps are frequently used in computer science to increase the complexity of different problems in a better order. We’ll talk about using maps to raise a problem’s order of complexity in this article.

There are numerous ways that maps can be utilized to increase a problem’s order of complexity. Below, let’s talk about a few of these methods.

1. Lookup tables: Making lookup tables is one of the most popular uses for maps. A lookup table is a type of data structure that has values that have already been calculated and are ready to use in an emergency. For instance, we may precompute the factorials and store them in a map if we need to calculate a number’s factorial more than once in a program. The factorial of a number may thus be easily retrieved whenever needed by using the map. This method can drastically lower the program’s order of complexity. Sets such as lookup tables are a good place to start since they allow us to simply store data and do simple searches on it. The three most utilized operations (search, del, and insert) are O(1).
2. Memoization: Memoization is the process of storing function call results so that they may be retrieved from the cache instead of having to be recomputed on subsequent calls with the same parameters. A map with the function parameters as the keys and the function results as the values can be used to implement memorization. Recursive algorithms can be made more efficient using memorization by eliminating the repetition of computing the same subproblems.
3. Two-pointers approach: Maps can also be used to implement the two-pointers approach. The two-pointers approach is a technique that involves iterating over a collection with two pointers or indices that move in opposite directions. The two pointers can be used to identify pairs of elements that satisfy a certain condition. For example, we can use the two-pointers approach to find all pairs of integers in a list that sum to a target value. To implement this approach, we can use a map to store the indices of the elements in the list.

How to recognise it:

While working through coding algorithms if you notice that in the problem there is to store key-value pairs that you can pull from or search through to help come up with an answer. Then maybe it is worth trying to utilize a hash map.

This will help you reduce the number of iterations.

Example Problem:

Problem: Given an array of integers, find the duplicate elements present in it.

An approach without HashMap/HashSet (O(n2))

One straightforward approach to solving this problem is by using nested loops. We can compare each element of the array with all the other elements to identify duplicates. However, this approach has a time complexity of O(n2) because, for each element, we need to iterate through the entire array.

function findDuplicates(nums) {
    let duplicates = [];
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === nums[j]) {
                duplicates.push(nums[i]);
            }
        }
    }
    return duplicates;
}

let nums = [1, 2, 3, 4, 5, 2, 4, 6, 7, 8, 5,2];
let duplicates = findDuplicates(nums);
console.log("Duplicate Elements: " + duplicates);

Approach using HashMap/HashSet (O(n))

By utilizing a HashMap or HashSet, we can significantly improve the efficiency of the algorithm. We can iterate through the array once, inserting each element into the data structure. If an element already exists in the HashMap/HashSet, we can conclude that it is a duplicate. This approach reduces the time complexity to O(n), as HashMap and HashSet offer constant time complexity for insertion and retrieval operations.

function findDuplicates(nums) {
    let frequencyMap = new Map();
    let duplicates = [];

    for (let num of nums) {
        if (frequencyMap.has(num)) {
            duplicates.push(num);
        } else {
            frequencyMap.set(num, 1);
        }
    }
    return duplicates;
}

let nums = [1, 2, 3, 4, 5, 2, 4, 6, 7, 8, 5];
let duplicates = findDuplicates(nums);

Let’s Analyse the time complexity:
The approach without HashMap/HashSet has a time complexity of O(n2) due to the nested loops, where n is the number of elements in the array. In contrast, the approach using HashMap/HashSet has a time complexity of O(n) as we iterate through the array only once and perform constant-time operations for insertion and retrieval.