case3's blog

TLE in Subarray Distinct Values
By case3, history, 4 years ago, In English

Hello everyone. This is a CSES problem: Subarray Distinct Values very simple and straightforward 2 pointer approach. My time complexity is O(n) visiting every array element almost twice. But I am getting TLE. Why.

My code: My Code on CSES

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

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

You can get ac by using map instead of unordered_map, nlog time complexity will work here. It is not necessary that every operation of an unordered_map will be of O(1) complexity. See this post by neal https://mirror.codeforces.com/blog/entry/62393 , you can use custom_hash in your unordered_map by neal to get ac.

→ Reply