ROBOT ROOM CLEANER | LEETCODE # 489 | PYTHON BACKTRACK SOLUTION
Vložit
- čas přidán 2. 05. 2022
- In this video we are solving yet another Google interview question: Robot Room Cleaner (Leetcode # 489).
This one on the surface looks easy because it's a pretty standard DFS based question until you realize that you aren't given a matrix/grid as input and instead need to work with the Robot class instead. We can apply the same principles as other grid DFS backtracking problems but we do need to be a little clever with how we actually execute the DFS. - Věda a technologie
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?
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
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.
Very nice work.
amazing explanation!!! thanks lot
why do you turn right after the loop? aren't you going to visit all directions regardless?
Thank you!
Thanks ser
At the end, because of go_back, Robot will return to its original position, right?
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.
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
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.
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