Loser_'s blog

Why O(n) solution gives me TLE?
By Loser_, history, 4 years ago, In English

In this problem , I take the input and I store every value in ith index to a map.If my map[i] has a value than I push both map[i] and i to a vector pair. Here in worst case the code may run in 2*n times which is so to say O(n)times.But how I am getting here TLE with O(n) times? My submission is here.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

std::map works for O(logn). and your time complexity is O((2 * N) * (2 * log(5000))). try to sort your array and find answer for O(N). total time complexity will be O((2 * N) * log(2 * N) + (2 * N)). it is will be work, imho

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

I made your solution pass by modifying a few things Submission

When using maps try to avoid using the []operator instead use count to avoid inserting extra values Reference
And I also used erase instead of setting the value to 0

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

Try using an array sized 5000, instead of std::map (that will be) sized 5000.

→ Reply