We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The idea is that we count 3 things:
1. Creating a dictionary with all added/removed values as keys and number of elements as values
2. Updating a frequency table
3. Result that we return in the end
Obvious solution would be to keep only the dictionary. However, then in case 3 every time we need to traverse the whole dictionary to check if there is a key with value that equals the search value;
It works fine on the initial tests but fails on the main set of tests because traversal of the whole dictionary is expensive.
OK, then we need to keep an extra list of frequencies. I used a simple array where the index is the number of occurencies, for example [0,2,3] means that there are 2 values which occur twice and 3 values that occur 3 times (dictionary in this case would be something like: {12: 2, 14: 3}
This way in case 3 I need only to check freq[number of occurencies]
Frequency Queries
You are viewing a single comment's thread. Return to all comments →
JavaScript solution (passes all tests):
The idea is that we count 3 things: 1. Creating a dictionary with all added/removed values as keys and number of elements as values 2. Updating a frequency table 3. Result that we return in the end
Obvious solution would be to keep only the dictionary. However, then in case 3 every time we need to traverse the whole dictionary to check if there is a key with value that equals the search value;
It works fine on the initial tests but fails on the main set of tests because traversal of the whole dictionary is expensive.
OK, then we need to keep an extra list of frequencies. I used a simple array where the index is the number of occurencies, for example [0,2,3] means that there are 2 values which occur twice and 3 values that occur 3 times (dictionary in this case would be something like: {12: 2, 14: 3}
This way in case 3 I need only to check freq[number of occurencies]