Search A Maze For Any Path - Depth First Search Fundamentals (Similar To "The Maze" on Leetcode)

Key Takeaways

[Applause] all right so today we have a fundamental graph question we don't see a graph here but the thing is whenever we have something with nodes with relationships with connections we can represent those connections and relationships with a graph and when you have a maze like this we can represent each of these cells as a node and each of the adjacent relationships as an edge whenever we can represent a node and an edge we are able to create a graph structure to make a representation of this that is what this is this is amazed and our interviewer says write-in algorithm to search this maze so if you're in an interview you're not gonna have to do any difficult algorithms like a star or something that's very efficient that works off of heuristics what you're going to have to do is you're gonna have to work from your fundamentals so we know our fundamental graph searching algorithms are going to be breadth-first search and depth-first search we're given us starts we're going to act and we're told to find a path we're not told to find the shortest path we're just tool to find a path find me a path in this maze so how will we do this now if I use breadth-first search i'm always going to get the shortest path from start to end why is that what breadth-first search does breadth-first search starts it's going to go outwards breadth it's going to go like this and then like that and then like that it's going to go layer by layer going outwards from the start so the thing is when we hit this end we're going to have gone out layer by layer and when we hit that end that means we're going to be in the layer that the end falls in so the thing is it's going to be the shortest path because of the nature of how we searched if we use depth-first search as we're going to see it's going to take us all the way in here it's going to take us all the way in here it's going to take us all the way there to the end it might not give us the shortest path but to give us a pack that's what depth first search will do for us I already have the video on depth first and breadth first graph search if you want to check that out check that out well what we're gonna do is we're gonna do depth-first search because it's fairly easy to implement and remember the code is in the description the code is in the description for this so if you want to see how the solution pans out how the recursion hands out you're free to go check that out I think it's a great resource so search this maze so when we're doing a search or whether it's grad first or depth first we need to understand our fundamental choice our fundamental choice at each of these cells what can we do at each of these cells each of these cells represents a choice so when I met any of these cells my fundamental choice is going to be go up go right go down or go to the left when can I not do these I can not do it if it's a black cell a black cell as a wall I cannot do it if I'm looking down and I met an empty Simon to sell out of the maze I can't do that so what I need to do is first understand my fundamental operations and second validates whether I can actually perform them if I'm sitting at this cell I can go up I can not go right I can no down but I can't go backwards why can't I go backwards well we're gonna be starting here at this start and we can't Traverse backwards in our path so every time we initiate a search from a node where we don't mark that node as searched we're going to mark that node as on traversable because we're performing the search off of it we can't go backwards in our path we're going to have an infinite recursion we're never going to find a path and everything's gonna be messed up so what we're gonna do is we're gonna kick off our search we're gonna start right here we're gonna mark this cell as Traverse and then what we're gonna do is say can I go up can I go right can I go down can I go left alright we marked a district this blue marker is going to put a little dot on the search we're going into deep so can I go up no I cannot can I go to the right yes I can let me go to the right that blue dot is telling me I'm going depth first I'm going deep into a search into here and if this doesn't work out I'm going to come right back here and then I'm going to link down and then I'm going to look left it turns out we can't go down or left but if this failed if this depth first search depth first failed we come back here and then we try down and then we try left but right now we're going depth first into right so what we're gonna do is we're gonna go to this right guy and now we're gonna mark a missed reversed and now what do we do what is our choice at every node we go up right down left can I go upwards of course I can we have a white cell that's clear we're not hitting a wall we're not going out about so what I do is I go depth-first and I put a dot okay and now you see we're going depth-first on here we're going deaf first upwards so all along this thing we're going to keep these in a path we're gonna keep it in an arraylist simple nothing new nothing complicated we're gonna keep this scenario let's keep this in a realist if it doesn't work out we'll just pop the item off and then we're not going to have to worry about it being in the path because it didn't work out so now we're up here can I go upwards yes I can but I want you to notice do you see the problem we're going to run into this is going straight to a dead end well we'll see how we handle that but the thing is this is why this is not kind of naive this is why these raw algorithms like depth-first research without you know pure States to sharpen them are are are naive because we'll go deep we'll go depth we'll go deep into this path and we won't even know this this is over here that is over there well why are we doing this but that's just the nature of the search so that's what I want you to notice in this so now we need a mark the sister verse can we go up the yes you can so now we're at this cell so now I'm mark the cells rivers can I go up no I cannot that's a wall can I go right no I cannot that's a wall can I go down no I cannot that is Arnie Traverse it's in our path can I go left yes of course I can I have a white cell here let's go left and again do you notice this is state do you notice how this is a recursive staff this is the call stack is keeping this information this call has information this calls state states each of these has their own state they're in their own little worlds I don't know what's going on over here all I know is that I'm going deep upwards I don't know what's going on here all I know is that going depth-first upwards each call stack is a state this is a fundamental recursive concept so now we need to go here and what do we do up right down or left can I go upwards of course I can all right now I'm at this so can I go upwards yes all right and then now I'm at this cell market is traversed can I go upwards yes I can let's do it all right now I'm at the cell above it market is reversed can I go above it yes I can okay now I look at the next cell market is reversed can I go up we noticed we can't we hit a wall can I go right of course I can it's a white cell let's do it and you see do you see how these are going deaf first keeping their states keep that in mind now we go here can be traverse it yes and now can we go up yes and now this is key I want you to notice this how we handle this dead end so we mark this can I go upwards no I can't can I go right no I can't can I go back no I can't can I go left no I can't this cell has exhausted its possibilities and you know what it returns to its caller it says I can't find a path for myself false I return false so this guy says okay you return false okay what do I do now what's my next state I just looked upwards and now where do I look I look to my right so now the cell this cell scrambling it's it's like what do I do next I let upwards now next it can I go right No can I go down no can I go left no I can't this cell then says hey guy who called me Hey this cell there's no path for me so what this cell does is it says okay okay so I just went right where do I go next now this cell looks down it can go down then it looks left it can't go left so what does it do tells its caller caller there's no path from and now do you see the blue taught on this guy who called it the blue dot was going down first upwards now the guy going upward says wait I just went up what's next what's next I go right can I go right from this guy no can I go down no can I go left no so what I do is I returned to my caller false my color scrambles he's like what do I do now I just went up so now he knows what to do look right you can't do it look down he can't do it look left he can't do it so then he returns to him and then this guy says okay next I look right no down no left no and then he returns to him and then he says right no down no left no so that if he has nowhere to go so then this cell sees that this cell tried all they tried right it tried down it just tried left so left didn't work out but what do you notice is this cell hasn't no more to explore it right should return Stuart's caller false I do not have a path for myself every call is a question hey cell do you have a path to the end hey cell do you have a path to the end when a cell finally has a path to the end it's going to return all the way back and then the first cell is going to say okay I know what the path is the call stack kept it the whole time from this cell we know we just tried upwards upwards did not work out upwards did not work out can we go right and I want you to notice here this is a huge realization we can go right and so every single action I just did every single action was me going upwards going deep into that path but now you notice we've tried everything from this cell the search rooted at this cell going upwards we've tried it all so now this cell went up what was next right can I go right of course I can and this is the fundamentals of depth-first search this is what I want you to grasp and every cell we have a choice we go deep into it if it does not work out we back out of it this is def first search these are the fundamentals we're at this cell and now we can go up right down or left so what we need to do is market is traversed and then what we can do is we can check can we go up right down left so can I go up no I can't can I go right of course again so again do you see how our path is adjusting itself do you see how we're slowly getting towards the answer and so now what we do is we check the cell can I go up no I cannot can I go right yes I can and then we are traversing this cell and then I ask myself can I go up yes I can and then I go up can I go up yes I can and then I'm at this cell and I need to mark it as traversed can I go up yes I can and then I'm at this cell I need to mark it as traversed can't I go up no can I go right no can I go down no can I go left yes and then I am at this cell can I go up yes and then I am at this cell can't I go up yes and then I am at this cell can't I go up yes and then I am at this cell can't I go upwards no I cannot go upwards can I go right yes I can and then I'm at this cell can I go up no can I go right yes and then I am at this so can I go up no can I go right no can't I go down no can I go left No so I return to this guy this guy realizes we're going right did not work so now he can go down remember that's our next step now we go down and then now I make this so can the cell go up no can it go right no can it go down no can it go left no so what we do is we have to go at backtrack we go to this guy down did not work out and then he says okay I try it down now I need to go left can I go left no so then this he returns to this guy there's no path for me he returns to him and then he says oh wait okay right didn't work out calm down it's fine now we can go down can we go down no can we go left no he returns to this guy up did it work out for it up did it not work out for it let's go right no down no left No so now we're here so now we're here up did not work out up did not work out goes right no down no left no now he returns to him up did not work out for this guy so now he goes right no down no left no so now he returns to his collar I have no pad for me and now this guy already tried left what's next nothing so this guy says there's no path from me either return to my collar now this guy said he went up it didn't work out so he goes right he can't do it he goes down you can't do it he goes left he cannot do it so now he returns to his collar his collar had just gone up so now he's gonna try to go right no he's gonna try to go down no he's gonna try to go left no so now he's going to return to his collar the next step for his collar his collar just tried up now he's gonna try to go right can we go right yes we can and as you can see from this you can see that we're almost home you can just take a straight path but let's keep walking through it so what's gonna happen is this guy's gonna go right we need a market can I go up I can't can I go right I cannot can I go down yes I can let's mark down okay we're right here now this guy says can I go up no I can't I'll go back on my path can I go right of course I can and now can I go up no I cannot connect oh right it's yes I can and now we're at this cell can we go up yes you can and now we're at this help can we go up yes we can and now we are at this so can we go up no can we go right no can we go down though can we go left yes and now we're at this so can we go up yes and now we're at this so can we go up yes and now we heard this so can we go up yes and now we are at this so can we go up yes and now we're this so can we go up no can we go right yes and now we're at this so can we go up yes and when we notices we've reached the end when we mark this cell so what this cell is going to do is it's going to realize this the act we visit this cell but we realize this cell is a base case this cell is the end so what does this cell dude this cell returns to its caller and it says I am the enemy well it doesn't really return to its caller sanity and but it returns to its caller saying I have a path and our base case if I am the end then I have a path to the end if this is the end then this returns to his collar it says hey I have a path to the end and then this guy says ok ok great we're I don't need to do anything else so let me tell the guy behind me I have a path to the end and then he says ok ok I have a path to the end I need to tell the guy behind me I have a path to the end and then this guy needs to tell the guy behind him I have a path to the end and then a few more of these guys it just keeps bubbling upwards and as you notice it keeps bubbling back upwards so this guy says I need to tell him I need to tell them him him him and then finally this was our top level call and now this guy's gonna say I need to tell them I have a path and then this guy is going to say hey original client who called my code I have a path and all the way along this path each note that was on the path is going to add itself and we are going to have the path from start to end this is how depth first search works I hope this was a clear tutorial thing so now let's go into time and space complexity and now for the time and space complexities they are fairly straightforward so V is the number of nodes in our graph or representation e is the number of edges are adjacent relationships per node these bars you see do see these bars bars mean cardinality I've always wondered what those bars meant until I took discrete math and you use that all the time it is just the amount of items in a certain set so if we have V equals of set of 5 nodes than the cardinality is 5 because it contains 5 items these bars mean cardinality so the time complexity is we're going to be traversing V nodes and we're going to be traversing e edges so that is why the time complexity of DFS is going to be V Plus E so our space complexity is going to be o of V our depth of our kallstadt at maximum the worst it can be is going to be the amounts of vertices in the graph or the call step or the path whether you can't output in space complexity or not but we know for sure our kallstadt at worst could hold every single vertice on the graph therefore we could have a call stack that deep so this is going to be our balance on our space that we could use so that's what this is all about if this was a clear explanation if this helped you understand something even a little more that is what this is all about that is why I do these I don't want people to Excel than the software engineering interview I want people to be their best and do their best so subscribe to the channel like this video if you liked the video and that is all [Music]