On the projects I’m working on, 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 employees, and an array of beers.
Each employee has a favorite beer. For each employee, we know his favorite beer because each employee has an attribute which is the id of his favorite beer.
Let’s say we want to print in the console, for each employee, his name and the name of his favorite beer.
The common implementation
Usually, common implementations for this problem looks something like that
Using the method find on the beers array, or an alternative, in order to loop for each employee through the beer array to find the beer 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 employees
- and for each employees we loop through the M beers to find his favorite beer
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 beers, 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 beers array, by setting the id as key and the beer as value.
Then, we replace the find on the beers array by a get on beersMap, and we are good to go.
Conclusion
The common implementation only use arrays, so it’s simpler and easier to understand.
The Map implementation is better in term of performance, but add a bit of complexity and require another step to create and fill the Map with the beers.
There is no real better solution, it’s a tradeoff you have to do depending of what you want 🙂
