Hello, Codeforces community,
I recently encountered a performance difference while solving a problem using an unordered_map and a vector, and I would like to seek some insights on this matter.
In my solution, I initially implemented the logic using an unordered_map to keep track of element occurrences. However, to my surprise, this implementation resulted in a Time Limit Exceeded (TLE) verdict. Curious about the issue, I refactored the code to use a vector instead, and the TLE issue was resolved.
Solution with Unorder_Map, Solution with Vector, Problem
I expected both implementations to perform similarly, as the time complexity of accessing elements in an unordered_map and a vector is generally O(1). However, it seems that the implementation with unordered_set resulted in a TLE, while the vector implementation passed the tests successfully.
I would greatly appreciate it if someone could explain why this performance difference occurred. Are there any particular reasons or considerations that make unordered_map less performant in this scenario? Any insights or suggestions would be valuable to me.
Thank you for your time and expertise.