TLE in 3 Testcases

#1

link to Code : https://ide.codingblocks.com/s/261072

My approach works in O(m*n), ans it should work as n & m are <= 1000, but it is still giving me TLE in 3 testcases.

Don’t give me the solution, I just want to know what am i doing wrong ?

#2

@O17LPOLA020011
Your logic is correct but time complexity of your code is little bit high. I am suggesting two thing, changing them will pass all testcase.

  1. your vis is a map, which have increased time complexity of your code by factor log(N*M). Change it to bool vis[1005][1005] and try implement using it.
  2. See line 77, here everytime you time you are creating new array v of size cur+1 which has increased space complexity as well as time complexity (time required to initialise whole array with zero). Declare it outside both loops.
#3

@O17LPOLA020011
I have updated your code as per above changes and it’s working for all cases. Check it here

#4

Thank you abhishek it solved the issue, got AC !

#5

@O17LPOLA020011
Please mark this doubt as resolved. Thanks

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.