TIME LIMIT EXCEEDED

#1

i am getting tle through my code. since constraints are large although i am solving it in O(n) complexity.
here is my code

#2

Hey @aditikandhway, you are not getting time limit error instead memory limit error because you are trying to store a large amount of values in the array .
I am sending you the correct code where the caching of the solution is done using a map .
In array we are trying to solve subproblem which we won’t even need to solve the actual problem .
So using a map saves a lot of time as well as space . this might be a new code for you . feel free to ping me if you don’t understand it .

#3

mark your doubt as resolved if it is resolved . thankyou
:blush:

#4

here you have done memoization using hash map instead of an array. right?? can you please explain me the line i mentioned in the code?h

#5

here is it https://ide.codingblocks.com/s/316568

#6

Yes Exactly and the subproblems which are not required are not being computed !

#7

It is doing the same thing as memoization
state[ans] = > same as arr[n] in memoization and the RHS is same .
ans here is the key of the map
and state is behaving as an array .
Hope you are clear now . If not , dry run once ,you will be able to clearly understand the solution

#8

okay i got that. THANK YOU!!

1 Like