I'm getting runtime error for this problem

#1

My code -

#2

hello @nidhigupta847

pls check ur updated code here->

a) u were creating very big size dp array thats why u were getting seg fault.

i have replaced dp array with M+1XN+1 vector .rest everything is correct

#3

Hey thanks. Also could you tell me the time complexity for this code ?

#4

time complexity for top down dp is defined as -> num of distinct states * transisition time

here in ur case num of distinct states are N*M and transisition time is O(1) { becuase from i,j u can only go to 4 new states which is constant time)

so it should be O(NM) * O(1) -> O(NM)

#5

Okay thanks. And what would the time complexity be in the case we had not used a dp array. Like if for every cell we had calculated dfs again n again for all the remaining cell ? I did that before writing this optimized code and it gave me a TLE. Would it be O( (mn)^2) ?

#6

yeah if u r keeping track of visited cells while making call from each cell then it will be (N * M)^2 (otherwise the program will stuck in infinite loop).
because from each cell (i,j) u can go to all other cells which (nm in numbers).
so for nm such cells it will be n * m * n * m.

#7

Thank you so much. You’re a great TA. Really appreciate your work.

1 Like
#8

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.