here is the link for the question :
here is my code.
i have used simple BFS starting from the first index and going till the last index.
this solution is passing all the test cases except for the last test case which shows time limit exceeded on submission but when i copy the testcase and run it, it gives some runtime error which i am not able to fix. can you please check what is the problem in my code?
In line 21 don’t start with i+1, instead maintain another variable which stores the maximum index of visited element (say max_vis) so now start from max(i+1,max_vis).
Also don’t forget to update max_vis.
its running now, but why is it happening if i have already kept the visited map?
its purpose is also this right? and moreover if i am removing the visited map and just using this maxvis variable, then it is again giving TLE. can you explain to me why is this happening?
i have updated the code in the above ide link which is without the visited map.
it is working with map only. neither with unordered_map, nor with vector and nor with bitset
see although you don’t insert element into queue more than once, still you iterate over visited elements again and again (this effectively brings your complexity up to O(NxN))
but then why isn’t it working without visited map?
it works even without visited map!
can you explain me your code a little bit? i am not able to understand why have you pushed -1?
is it to denote a new level? also can you point out the mistake in my code? because the same code is working with a visited map but somehow it isn’t working without a map
yes of course -1 is for the counting level(minimum steps to reach end),
also visited map is not required as it is understood that all elements from 0 to max_vis are visited.
yes but can you point out the mistake in my code as it is giving TLE without a map even after keeping a visited variable
In line 25 start with x+1 instead of i+1.
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.