ParthJha17's blog

By ParthJha17, history, 17 months ago, In English

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.

  • Vote: I like it
  • -7
  • Vote: I do not like it

| Write comment?
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.