Can anyone suggest quicker way?🙃

Question

Hey guys, i got a problem you can read it link below

https://quera.org/problemset/132247/

The question has a time limit and it causes to not pass all tests, if you know a better solution,please let me know
(You can send your solution in any programming languages) by the way subscribers for sending your questions to site
https://code.sololearn.com/c7lE5Hl35sor/?ref=app

Answer 1

Your speed problem is most like due to the use of the vectors' remove(Object o) method. While the remove(int index) version has a lookup in constant time the former is linear. This means that you actually have a time complexity around O(n²).
If the names were unique I would suggest you use a set instead. However, due to name duplication, this approach wouldn't work. So, you may want to use something more like a hashmap, dictionary etc to get a constant lookup time. The trade off will be that it uses a bit more memory. You can then use an int as the value for the name as the key, to track how many duplicates of that name. As you add them, check if they are already in the map. If so increment their value by 1. If not add them with an initial value of 1. As you go through the second loop decrement their value. If their value drops to 0 you can delete them from the map or after the second loop you can then loop through the map to find the name that has a value of 1. You'll need to test which way is faster.