Can you explain the intuition behind how one would figure out why a normal DFS (where you loop through directions) wouldn't work and instead need to setup the i % 4 step?
There is a little bit of intution that is involved. Consider the following example and this would make it much more clear. (Because I had the same thought as you) Let's say the robot is facing upwards and wants to move to the next part of the dfs call. (UP -> RIGHT -> DOWN -> LEFT, in this clockwise order) So, looping through the directions array and finding the next direction is a way to find the coordinate of the new direction that the robot eventually wants to go, but as the robot can ONLY move in the direction it is facing, we have to take a right turn before calling move in the loop. I hope this explains the situation. Let me know if you still have questions.
The 4 directions in the for loop are for our reference to store in the visited array. The robot doesn't move based on coordinates, it moves based on where it is pointing to, that's why we turn it at every step.
This is a really difficult problem but you explained it well and thoroughly. I dont think I would be able to remember how to solve this or able to solve it in time during an interview though
@@crackfaang gotcha. This is the best solution to the problem out there So I'll memorize it. One issue I'm facing is the top meta questions keep changing. So it's going to be a challenge.
@@rsKayiira You're worrying about nothing here if I have to be honest. The questions may move up and down the rankings but it's all largely the same. Maybe down past like the top 120 there's movement but those are so infrequently asked that even 1 person reporting they got it in an interview will make it shoot up the rankings. If you look at Meta's questions they are basically all Mediums/Easies. With Meta the question selection is very easy but you are expected to solve two questions and breakdown the problem and communicate your thoughts clearly. I'd focus more on mastering the top 75 and being able to explain them perfectly out loud before starting to worry about anything lower down on the list. Knowing questions from 75-150 is more of an insurance policy against getting some random question.
@@crackfaang What are the odds that I solved 300 of the 310 Meta questions and I got 2 questions outside of this list of 300? My luck is such, that I got 1 question from the remaining 10 that I did not prepare for, and the other was not even on leetcode.
That’s not the right explanation, -1,0 in the directions is the differential to go up. Since you’re reducing the row on the same column, you will travel up if you add this direction to your position ( differential )
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)] are (left, up, right, down) and not those mentioned in the code but I have seen solutions with incorrect direction comment on multiple sites :( unfortunately lot of folks are simply restating same mistaken explanation without understanding
This is so far the best walk through for 489.
Can you explain the intuition behind how one would figure out why a normal DFS (where you loop through directions) wouldn't work and instead need to setup the i % 4 step?
I don’t get why you would turn right on line 32 after the goBack. You are already going in every direction when you for loop through the 4 directions.
There is a little bit of intution that is involved.
Consider the following example and this would make it much more clear. (Because I had the same thought as you)
Let's say the robot is facing upwards and wants to move to the next part of the dfs call. (UP -> RIGHT -> DOWN -> LEFT, in this clockwise order)
So, looping through the directions array and finding the next direction is a way to find the coordinate of the new direction that the robot eventually wants to go, but as the robot can ONLY move in the direction it is facing, we have to take a right turn before calling move in the loop.
I hope this explains the situation. Let me know if you still have questions.
The 4 directions in the for loop are for our reference to store in the visited array. The robot doesn't move based on coordinates, it moves based on where it is pointing to, that's why we turn it at every step.
What an explanation! Thank you for this!
Thank you for much for making videos for these hard questions!!!
No problem! Subscribe so you don’t miss future videos
This is a really difficult problem but you explained it well and thoroughly. I dont think I would be able to remember how to solve this or able to solve it in time during an interview though
As long as you understand the intuition, this is one you can basically memorize if you are having trouble remembering the code
@@crackfaang gotcha. This is the best solution to the problem out there So I'll memorize it. One issue I'm facing is the top meta questions keep changing. So it's going to be a challenge.
@@rsKayiira You're worrying about nothing here if I have to be honest. The questions may move up and down the rankings but it's all largely the same.
Maybe down past like the top 120 there's movement but those are so infrequently asked that even 1 person reporting they got it in an interview will make it shoot up the rankings.
If you look at Meta's questions they are basically all Mediums/Easies. With Meta the question selection is very easy but you are expected to solve two questions and breakdown the problem and communicate your thoughts clearly.
I'd focus more on mastering the top 75 and being able to explain them perfectly out loud before starting to worry about anything lower down on the list. Knowing questions from 75-150 is more of an insurance policy against getting some random question.
@@crackfaang Okay got it thank you!! Looking forward to more content.
@@crackfaang What are the odds that I solved 300 of the 310 Meta questions and I got 2 questions outside of this list of 300? My luck is such, that I got 1 question from the remaining 10 that I did not prepare for, and the other was not even on leetcode.
At the end, because of go_back, Robot will return to its original position, right?
Very nice work.
amazing explanation!!! thanks lot
I think in your directions array you are starting from all the way left then up,right,down its still a clockwise movement
That's right. Direction starts from left in clock wise manner.
thank you! I was so confused as to how (-1,0) is up.
That’s not the right explanation, -1,0 in the directions is the differential to go up. Since you’re reducing the row on the same column, you will travel up if you add this direction to your position ( differential )
why do you turn right after the loop? aren't you going to visit all directions regardless?
Needs to go to right direction after coming back to original direction.
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)] are (left, up, right, down) and not those mentioned in the code but I have seen solutions with incorrect direction comment on multiple sites :(
unfortunately lot of folks are simply restating same mistaken explanation without understanding
I think it's (row, col) not (x, y) so it is correct
Both time and space complexity are exponential in backtracking.
No that's not always true. In this case it's not and the complexity is O(N-M). You can check the Leetcode solution if you don't believe me
Thank you!
Thanks ser