ROBOT ROOM CLEANER | LEETCODE # 489 | PYTHON BACKTRACK SOLUTION

  Рет қаралды 12,105

Cracking FAANG

Cracking FAANG

Күн бұрын

Пікірлер: 32
@zongjunliu7211
@zongjunliu7211 2 жыл бұрын
This is so far the best walk through for 489.
@yynnooot
@yynnooot 10 ай бұрын
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
@ByteVenture 9 ай бұрын
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
@ferbot123 2 ай бұрын
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.
@pria_xoxo
@pria_xoxo 11 ай бұрын
What an explanation! Thank you for this!
@seant11
@seant11 6 ай бұрын
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?
@cindysu262
@cindysu262 2 жыл бұрын
Thank you for much for making videos for these hard questions!!!
@crackfaang
@crackfaang 2 жыл бұрын
No problem! Subscribe so you don’t miss future videos
@VerghisKoshi
@VerghisKoshi Жыл бұрын
Very nice work.
@kostyaverein5258
@kostyaverein5258 2 жыл бұрын
At the end, because of go_back, Robot will return to its original position, right?
@rsKayiira
@rsKayiira 2 жыл бұрын
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
@crackfaang 2 жыл бұрын
As long as you understand the intuition, this is one you can basically memorize if you are having trouble remembering the code
@rsKayiira
@rsKayiira 2 жыл бұрын
@@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
@crackfaang 2 жыл бұрын
@@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
@rsKayiira 2 жыл бұрын
@@crackfaang Okay got it thank you!! Looking forward to more content.
@square-kstudios9561
@square-kstudios9561 8 ай бұрын
@@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
@oitejjhoamlan6022 11 ай бұрын
amazing explanation!!! thanks lot
@shrutimistry2086
@shrutimistry2086 6 ай бұрын
why do you turn right after the loop? aren't you going to visit all directions regardless?
@carefree_ladka
@carefree_ladka 4 ай бұрын
Needs to go to right direction after coming back to original direction.
@mashareznik4117
@mashareznik4117 7 ай бұрын
Thank you!
@eddiej204
@eddiej204 2 жыл бұрын
Thanks ser
@geekydanish5990
@geekydanish5990 2 жыл бұрын
I think in your directions array you are starting from all the way left then up,right,down its still a clockwise movement
@komalgujarathi8900
@komalgujarathi8900 2 жыл бұрын
That's right. Direction starts from left in clock wise manner.
@sumeetkamat
@sumeetkamat 5 ай бұрын
thank you! I was so confused as to how (-1,0) is up.
@ronakshah725
@ronakshah725 4 ай бұрын
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 )
@dabaaku
@dabaaku 6 ай бұрын
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
@dmitricherleto8234 5 ай бұрын
I think it's (row, col) not (x, y) so it is correct
@arleo09
@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
@user-vm8fv6nm6k Ай бұрын
@@arleo09 guess its the index of those 4 directions. not able to set/show the data type explicitly
@marjanramin1769
@marjanramin1769 6 ай бұрын
Both time and space complexity are exponential in backtracking.
@crackfaang
@crackfaang 6 ай бұрын
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
DIAGONAL TRAVERSE | LEETCODE # 498 | PYTHON SOLUTION
12:57
Cracking FAANG
Рет қаралды 14 М.
It’s all not real
00:15
V.A. show / Магика
Рет қаралды 20 МЛН
Каха и дочка
00:28
К-Media
Рет қаралды 3,4 МЛН
Правильный подход к детям
00:18
Beatrise
Рет қаралды 11 МЛН
Robot Room Cleaner (LeetCode 489 - Hard)
24:56
TechMockInterview
Рет қаралды 5 М.
How I would learn Leetcode if I could start over
18:03
NeetCodeIO
Рет қаралды 786 М.
5 Python Libraries You Should Know in 2025!
22:30
Keith Galli
Рет қаралды 85 М.
Dependency Injection, The Best Pattern
13:16
CodeAesthetic
Рет қаралды 909 М.
The unfair way I got good at Leetcode
6:47
Dave Burji
Рет қаралды 528 М.
Fast Inverse Square Root - A Quake III Algorithm
20:08
Nemean
Рет қаралды 5 МЛН
Robot Room Cleaner | Leetcode 489 | DFS & Backtracking | HARD
14:50
Arpan Pathak
Рет қаралды 1,3 М.
The Absolute Best Intro to Monads For Software Engineers
15:12
Studying With Alex
Рет қаралды 679 М.
How to Solve ANY LeetCode Problem (Step-by-Step)
12:37
Codebagel
Рет қаралды 342 М.
Dynamic Programming isn't too hard. You just don't know what it is.
22:31
DecodingIntuition
Рет қаралды 239 М.
It’s all not real
00:15
V.A. show / Магика
Рет қаралды 20 МЛН