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.
Two operations can have the same time complexity but still perform drastically different. For example, $$$f(n) = n + 3$$$ and $$$g(n) = 20 n + 100$$$ are both $$$\mathcal{O}(n)$$$. There is a higher overhead of operations in unordered_map so even if you are not experiencing hash collisions, you may still get TLE using unordered_map but AC with vector/array. Without seeing your code, I would guess that a high number of hash collisions are the main cause since N is not that large.