ved_vijay_d's blog

TLE when using vector instead of map
By ved_vijay_d, 4 years ago, In English

I used a vector of strings to solve this problem — https://codeforces.net/problemset/problem/4/C

I got a TLE on this, afterwards I saw some other people used map instead of a vector. Could someone kindly inspect my code and explain where I went wrong and tell me why using map is better. My code — https://codeforces.net/contest/4/submission/85707717

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

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Both find and count take O(n) for a vector, but O(log n) for a map. Generally if you need to check if something exists quickly, you should use a map or set.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

find is $$$O(N)$$$, so you code runs in $$$O(N^2)$$$. I would imagine that find just does a for loop until it finds the element. map::count and map::find both work in $$$O(\text{log}(N))$$$ because of the way map works (the keys are ordered). I think the use case for vector over map is when you only need to store things with indices small enough so that the vector doesn't consume too much memory, e.g. frequencies of characters in a string or values of some function.

→ Reply