Search A Maze For Any Path - Depth First Search Fundamentals (Similar To "The Maze" on Leetcode)
HTML-код
- Опубликовано: 18 янв 2019
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given a 2D array of black and white entries representing a maze with designated entrance and exit points, find a path from the entrance to the exit, if one exists.
Graph search methodologies apply well to problems that have an aspect of a spatial relationship.
Approach 1 (Brute Force)
We could try to enumerate all possible paths in the maze from the start to the finish and then check all paths to see if any of them are valid (have all white squares, aka do not run over a wall).
This is both naive and extremely costly in terms of time.
Approach 2 (Graph BFS or DFS)
We will imagine each cell as a vertex and each adjacent relationship as the edges connecting nodes.
Do we use DFS or BFS?
If we use BFS we know that the path that we find will be the shortest path because of how it searches (wide, going out layer by layer).
If we use DFS we can have the call stack remember the path making things easier to implement.
If we hit the end cell, then we will know that every call below in the call stack has a node apart of the answer path.
Since the problem just wants any path then we will use DFS since it is more straight-forward.
Complexities
Time: O( | V | + | E | )
The standard time complexity for DFS
Space: O( | V | )
We will at maximum the length of the path on the call stack through our recursion
Note: The problem on Leetcode requires BFS to pass because DFS will not always find the shortest path, but I did DFS in this video just for teaching purposes.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 19.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. 
Наука
Table of Contents:
Leave The Library Plz 0:00 - 0:17
The Problem Introduction 0:17 - 2:50
Our Fundamental Operations 2:50 - 3:50
Beginning The Depth-First Search 3:50 - 7:26
We Hit Dead End #1 7:26 - 9:50
We Get Back On Track 9:50 - 12:03
We Hit Dead End #2 12:03 - 13:27
We Get Back On Track Again 13:27 - 14:31
We Reach Our Target: The End 14:31 - 15:00
Returning Back Upwards With The Path 15:00 - 15:28
The Top Level Caller Gets The Path 15:28 - 15:59
Time Complexity 15:59 - 16:42
Space Complexity 16:42 - 17:09
Wrap Up 17:09 - 17:30
The code for this problem is in the description. Fully commented for teaching purposes.
code is missing
The repository is deprecated - we only maintain backtobackswe.com now
@@BackToBackSWE Is it possible for you to share the link to this code ?
@@punitpawar4231 I wonder this as well
yes it would be wonderful if you just provide the code link
Bruh, your lectures are WAY clearer and more concise than some of the “best” professors I’ve encountered.
Kudos to you!
thx
I thought he was a professor ... and he's just a student. Really good explanations.
You and Abdul Bari are the kings of explaining algorithms and problem solving. Thanks a LOT for everything you do!
Damn true
NeetCode, DEEPTI TALESRA, Jenny's Lectures CS IT, Tushar Roy - Coding Made Simple, Nikhil Lohia too.
I really like that you explain things in such a simple way and teaches the most fundamental method. As a matter of fact, it is always most difficult to learn the most fundamental stuff.
thanks.
Man, you are an excellent teacher. I stumbled onto one of your videos earlier and immediately started up another, right after. I'm about five videos in, now.
I've got books upon books about algorithms, I've read articles, related papers, tutorials, pseudo-code implementations, and public code-bases on software repo's, but this is the first time I've gained a simple, clear intuition for some of these concepts. Thank you so much for taking the time to make these videos. I'll refer people to your content any chance I get.
Sure - thank you.
Best explanation I've seen of DFS so far. I wish my professors explained things this way. I likely would have dropped out of my MSc if it wasn't for your channel!
dang, nice!
Big thanks to you! Currently I am a bit angry that my university is not capable of explaining such stuff in a nice way, but you did it in less time and in a much clearer way!
Best Explanation for DFS I've come across so far. Thanks a lot !!!
Keep up the good work guys.
thx
The call stack is a state! So brilliant words!
ye
Yes...it cud be completed or uncompleted(waiting for child stack to complete)
This is so clear to me, I’m amazed at how easy you make this to understand
nice
I saw the BFS & DFS (15 min) video followed by the maze problem. Wow! It clears out when and where to chose BFS over DFS. Thanks a LOT!
sure
Just amazing. I'm really grateful for your work
long way to go...very very very very long way
@@BackToBackSWE Don't forget to enjoy the journey :)
This was fantastic. Thank you so much for such a clear, effective explanation of recursive DFS algorithms for maze traversal!
sure!
Till now, your video is still saving lives. I finally completed my damn maze assignment after your explanation. Wherever you are bro, THANK YOU!!!
Thanks so much for the video! This makes so much more sense now
This dude is a brilliant tutor. Never have i ever understood an algorithm this clearly, Juss did.
Hey man, after listening to your excellent explanation, I was able to go and code this up! Thanks! You are a really good teacher!
sure
keep posting videos, I would love to see more of this
ok will do
Honestly, you sitting in front of a computer would be a waste of talent! Take advantage of your skill to explain complex stuff the easy way and make a business out of it.
👀👀💰💸💰
@@BackToBackSWE start a university with only you as teacher
@@jonathandaniel7321 I do not want to do that.
Awesome explanation! Very clear and the right amount of details
Great information 💪🏽💯 I appreciate it
the visualizations are really fantastic. awesome work ben :)
thx
Brilliant - clear and concise!
The way you explain is simply amazing sir!
Dude thanks for thee constant repition. Really helped cement how depth first search works
Glad to hear that! explore our 5 day free mini course for some cool content - backtobackswe.com/
Beautiful video, you just earned a subscriber. I really admire your content!!!
thx
How did you convert the maze to adjacency matrix to apply DFS? Doesn't it seem difficult? Actually, do you have a cpp code for that? Thanks in advance
Great content! Keep up the good work!!
ok
WOW. best explanation so far. After this I am gonna do Maze I, II and III on Leetcode. I got asked this for Amazon OA and i screwed up cuz my fundamentals were not good. thanks
nice and sure
The great video. Thank you so much for your contribution. Keep continuing making this type of video. Thumbs up !
sure
I'm currently having a problem with implementing DFS in ruby, and have had it for a week now. Is there a way to get the code out of this video anymore?
Hello, sir you have high degree of patience to expain each and every minute detail. And I wish you will soon reach your traget of 100K subscribers and keep it up.😀
thx
@@BackToBackSWE hi, would love help on mazes
appreciate it man, well explained.
sure
you explained so well, thank you!
sure
What's the main pros and cons of doing this in BFS and DFS? I thought DFS would be better, but it seems like only BFS is accepted on Leetcode. What are your thoughts? Also, do you think we should also know how to do Dijkstra for these kinds of search questions but with weights?
BFS always finds the shortest path. The reason DFS times out is because it will get really far from the answer and waste time.
BFS will find the object faster...generally...think about it...BFS goes out level by level and doesn't go deep into anything. This is good and bad.
Ponder on these things.
Thank you, your explanations are great!
sure and thanks
Your patience is admirable
Thank you so much for this! Very clear and concise explanation of DFS.
sure
What the decimals please?
Hey can you explain why the time complexity is V+E. We are checking 4 (i.e. E) edges for each vertices(V). So shouldn't the complexity be 4V i.e. V.E?
One of the best explanation of maze problem... Beautiful
thanks
That was a very clear explaination.Keep it up ! 😊
ok
Hey! Great video! What;s the difference between DFS and Backtracking on this problem? Cant both be used and wont both work the same way?
DFS is a search methodology.
Backtracking entails looking at candidate solutions in an exhaustive way (often following a search path) and "backtracking" to abandon partial solutions once they can't lead to a final solution.
Both can happen at the same time. Example: "Search a graph for paths from the start to the end with cost < 100, no nodes have a negative cost." If I am on a path and my cost hits 140 I could be deep into a path (if I am using DFS) but I'd backtrack to the previous node I was at since I can't recover (i shouldn't have stepped on the next node in the first place but you get the idea).
Thank you for saving us!
Best explanation of DFS. Thanks a lot. God bless you
sure
Thank you. i fully grasp it.
nice
Great work!
May I ask, if you are given an adjacency matrix of m x m, in that case what would be the time complexity of DFS path finding algorithm? Could you also explain?
Sure, this search should give you what you need: www.google.com/search?q=DFS+with+adjacency+matrix+time+complexity&oq=DFS+with+adjacency+matrix+time+complexity&aqs=chrome..69i57j0l5.7645j1j7&sourceid=chrome&ie=UTF-8
Could this algorithm change the numbers in the array on the way it finds?
So amazing! Thanks!
"Can I go up, yes I can!" is going to be looping in my head for a week after this video
Your vids are brilliant.
Thanks! this is useful, im currently making a game which npc will randomly trigger travel event, but i need the npc to calculate the clear path to the end and avoid crash into
rock and hill 😂
hey man , i'm the one who asked for minimum window substring on leetcode . just wanna tell you that you doing a pretty good job and this channel HAS the potential. keep coming up with these videos and if possible with python language .
cheers!
hmmmm, yeah, good idea. I need to brush up on my Python though. My languages in order of strength: Java, Typescript (a superset of course), Javascript ...then some experience with C, C#, Ruby
@@BackToBackSWE n i think it'll also be a good idea if you specify the difficulty level before the video . for eg :- easy , medium , hard on leetcode ,
@@ravitanwar9537 Every video has badges of the difficulty.
Where is the code for the DFS approach
If I want to use the DFS to generate a maze in C++, and not necessarily solve it, how should I think and start out?
Thanks for the great video!
sure and you can google that?
Amazing as usual.
thanks haha
Subscribed the channel, Liked the video, it deserves it.
thanks a lot man
sure
you have an amazing skill of teaching, even 10 years old can understand your explanation.
thanks
Very good, thanks !
Thanks bro!
The video goes in-Depth of the topic literally and thus my search for DFS is complete :p
nice
this is amazingly amazing explanation. thnx buddy
Doing the lords work with these videos! Thank you!! Lol
If I'm not mistaken, this approach is backtracking, right? And its complexity is to the exponential order of 2^(n*m) where n*m is the order of the matrix, but for a vanilla DFS we should have linear complexity, O(m*n)
Big Thanx
thanks for this great video.
sure
Is the code available for this dfs?
Maaan, you are the legend. Thank you for your brilliant explanation!!!
Happy Halloween 🎃 Thank you from one legend to another, kirillzlobin! You get some extraaa treats - 50% Off our exclusive lifetime membership use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50
Amazing explanation, but not able to find the code in the description.
The best explanation on the internet.
That's nice of you
Excellent,,tnxx for this good video
sure
I have a question , i am making a micromouse but how will it know the end ?? Does i have to pre program the final destination and the maze size??
I think there are three ends! How will my mouse knows which one is the final end??
Awesome explanation
Thanks man
sure
This helped me a lot!! I love the way you teach. Thanks. Subscribed immediately
Edit: The code below is my version of DFS for a maze problem and the concept is based on this video. Appreciate it.
function solve(lines) {
let wAndH = lines.shift();
wAndH = wAndH.split(' ');
let [w, h] = wAndH;
w = Number(w);
h = Number(h);
let nestedArr = lines.map(item => {
let a = [];
a.push(item);
return a;
})
nestedArr = nestedArr.map(item => {
return item[0].split("");
})
let blockStart = [];
let blockEnd = [];
for(let i = 0; i < w; i++){
blockStart.push('#');
blockEnd.push('#');
}
nestedArr.splice(0, 0, blockStart)
nestedArr.splice(h+1, 0, blockEnd);
nestedArr.forEach(item => {
item.unshift('#');
item.push('#');
})
let roadCoordinates = [];
function findRoad(arr = [], h = 0, w = 0, road) {
const checkUp = (arr, h, w) => {
if(arr[h-1][w] === '.') {
return true;
} else {
return false;
}
}
const checkRight = (arr, h, w) => {
if(arr[h][w+1] === '.') {
return true;
} else {
return false;
}
}
const checkDown = (arr, h, w) => {
if(arr[h+1][w] === '.') {
return true;
} else {
return false;
}
}
const checkLeft = (arr, h, w) => {
if(arr[h][w-1] === '.') {
return true;
} else {
return false;
}
}
if(arr[h] != 'undefined') {
if(arr[h][w] === '.') {
if(checkUp(arr, h, w)) {
arr[h][w] = '1';
road.push([w,h])
findRoad(arr, h-1, w, road);
} else if(checkRight(arr, h, w)) {
arr[h][w] = '1'
road.push([w,h])
findRoad(arr, h, w+1, road);
} else if(checkDown(arr, h, w)) {
arr[h][w] = '1'
road.push([w,h])
findRoad(arr, h+1, w, road);
} else if(checkLeft(arr, h, w)) {
arr[h][w] = '1'
road.push([w,h])
findRoad(arr, h, w-1, road);
} else if(arr[h][w] === '.') {
arr[h][w] ='1';
road.push([w,h])
}
} else {
console.log('Wrong')
}
}
}
findRoad(nestedArr, 1, 1, roadCoordinates)
nestedArr.pop();
nestedArr.shift()
nestedArr.forEach(item => {
item.pop();
item.shift()
})
roadCoordinates.pop();
console.log(roadCoordinates.length)
}
great, thanks, sure, and great
I really liked your video +1 Subscribed!!
thx
Excellent !
thanks
Great Explanation!! would be better with some pseudo code!! Else found it really helpful. Thanks!!
nice
U hv given a greatest explanation i ever had on RUclips..but implementation is also important right..plz do explain codes as well
Where is the solution code please give me the link
The respository is deprecated - we only maintain backtobackswe.com now.
dude I hecking love you, if I get the offer I'll definitely donate the shit out of u
Don't, just get the offer.
Best explanation !!
thanks
Is the code posted applicable for both BFS and DFS approach?
I think it was a dfs?
thank you
sure
"AND NOW WE ARE THIS CELL" ........that is a drinking game right there...number of times that was said, man would be wasted in no time...cool tutorial bro .. keep it up
hahahahahahaha
I want to ask how did you decide the order of the operations "up","right","left",down" , is it because you compared the starting cell and the goal/end cell and found out you should prioritize "up" and "right" operations ? so thats why they are at the top of the order of the operations and you check on them first?
and can you please provide me the of the code that corresponds to this problem
wow thanks so much this helped
appreciate the comment 😄 Would love to hear your thoughts about our FREE DSA course at backtobackswe.com/ 💯
Your delivery and presentation is just on POINT. I don't like it, I LOVE IT. You helped me tackle a PACMAN PROBLEM USING THE UNIFORM-COST SEARCH BY JUST WATCHING THIS VIDEO
Sir,In some cases time limit exceeded, how to overcome it ?
thanks bro
I don't usually leave likes on videos but you deserve it my guy.
Awesome explanation sir!!!
sure
Best explanation🖤
Amazon asked me this in the phone interview and even though I knew it I promptly fucked it up.
Eh, whateves
Where is the code?
Woa, you just got my sub!
P.S do you have the code available? I can't find it
Thanks, and the code repository is deprecated - we only maintain backtobackswe.com now.
clear explanation
thx
Is there a way I could see the code? Do you have a repo by any chance?
We only maintain code samples on backtobackswe.com
For a maze where we also have a given start point. Isn't dfs time complexity O(V) and not O(V+E) here ?
It is always O(V+E) even given the start