ROBOT ROOM CLEANER | LEETCODE # 489 | PYTHON BACKTRACK SOLUTION

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.

[@zongjunliu7211]

This is so far the best walk through for 489.

[@yynnooot]

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.

[@ByteVenture]

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.

[@ferbot123]

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.

[@seant11]

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?

[@pria_xoxo]

What an explanation! Thank you for this!

[@cindysu262]

Thank you for much for making videos for these hard questions!!!

[@crackfaang]

No problem! Subscribe so you don’t miss future videos

[@VerghisKoshi]

Very nice work.

[@rsKayiira]

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]

As long as you understand the intuition, this is one you can basically memorize if you are having trouble remembering the code

[@rsKayiira]

@@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.

[@crackfaang]

@@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.

[@rsKayiira]

@@crackfaang Okay got it thank you!! Looking forward to more content.

[@square-kstudios9561]

@@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.

[@oitejjhoamlan6022]

amazing explanation!!! thanks lot

[@kostyaverein5258]

At the end, because of go_back, Robot will return to its original position, right?

[@shrutimistry2086]

why do you turn right after the loop? aren't you going to visit all directions regardless?

[@carefree_ladka]

Needs to go to right direction after coming back to original direction.

[@geekydanish5990]

I think in your directions array you are starting from all the way left then up,right,down its still a clockwise movement

[@komalgujarathi8900]

That's right. Direction starts from left in clock wise manner.

[@sumeetkamat]

thank you! I was so confused as to how (-1,0) is up.

[@ronakshah725]

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 )

[@mashareznik4117]

Thank you!

[@eddiej204]

Thanks ser

[@dabaaku]

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

[@dmitricherleto8234]

I think it's (row, col) not (x, y) so it is correct

[@arleo09]

@@dmitricherleto8234 it is a direction, how can it be modeled by a row ? Genuine question, because I had a hard time understanding. My initial thought was like the OG comment because of trigonometry rules, which make much more sense intuitively imo.

[@user-vm8fv6nm6k]

@@arleo09 guess its the index of those 4 directions. not able to set/show the data type explicitly

[@marjanramin1769]

Both time and space complexity are exponential in backtracking.

[@crackfaang]

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