ankit_201's blog

Why unordered_map Can Cause TLE in C++
By ankit_201, history, 13 months ago, In English

unordered_map offers average O(1) time for insert, find, and erase ,it can still cause Time Limit Exceeded (TLE)

1. Worst-Case Complexity is O(n)

Hash collisions can degrade performance from O(1) to O(n), especially with poor key distribution.

Use map (O(log n)) for consistent performance.

Add your knowlesge ..

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nice

→ Reply
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

good

→ Reply
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Thats all because of hash collision, all numbers going to one bucket. But if you want to use unordered_set or unordered_map, you should have a custom hash function, which you get from GPT, but not in contest. You can do it out of contest, like write your template.

→ Reply