Reducing time complexity using a map

Reducing time
complexity using a Map.

Map in JavaScript
In this article, we would be discussing Map object provided by ES6. Map is a collection of elements where each element is stored as a Key, value pair. Map object can hold both objects and primitive values as either key or value. When we iterate over the map object it returns the key, value pair in the same order as inserted.

Map (using Binary Search Tree)

1. O(log(n)) **** Implemented using Binary Search Tree**** For more reference

I sometimes see this kind situation:
We are looping through an array, and for each element of this array, we are looking into another array to find some data related to this element (or sometimes several other arrays to find more data).
Example
Let’s say we have an array of animals, and an array of cat.
Each animals has a favourite cat. For each animals , we know his favourite cat because each animals has an attribute which is the id of his favourite cat.
Let’s say we want to print in the console, for each animals , his name and the name of his favourite cat.
The common implementation
Usually, common implementations for this problem looks something like that.
Using the method find on the cats array, or an alternative, in order to loop for each animals through the cat array to find the cat we are looking for.
It’s clear, simple, and it works. So that’s nice.
But if we check at the time complexity, it’s not that nice:
we loop through the N animals
and for each animals we loop through the M cats to find his favourite cat
So the time complexity is O(N*M).
And the space complexity is O(N+M) because we have N+M elements to store in memory.
We can do better
By using a Map instead of an array to store the cats, we are going to reduce the time complexity to O(N), without increasing the space complexity. Why ? Because accessing a value with the get method of a Map (in practice) is constant in time (O(1)).
First, we create a Map from the cats array, by setting the id as key and the cat as value.
Then, we replace the find on the cats array by a get on catsMap, and we are good to go.
Conclusion
Using javascript in built function is always a better choice since it is a higher order function. Instead of using for loop for iteration.