**Graphs and Island Hopping: A Deeper Dive**

While graphs are a fundamental concept in computer science and mathematics, they can sometimes seem daunting due to their complexity. However, with a clear understanding of graph theory and algorithms, we can tackle even the most challenging problems. In this article, we will explore the world of graphs and discuss one specific problem that requires graph theory: finding the minimum size of an island in a given grid.

**Understanding Graphs**

Before we dive into the specifics of the island hopping problem, let's take a moment to review what graphs are and how they work. A graph is essentially a collection of nodes (also known as vertices) connected by edges. Each node can represent a location or a piece of information, while each edge represents a connection between two nodes. Graphs can be represented using various notation systems, such as adjacency matrices or adjacency lists.

**Depth-First Search and Island Hopping**

When dealing with graphs and island hopping problems, one common algorithm is the depth-first search (DFS) algorithm. This algorithm works by traversing the graph in a depth-first manner, exploring as far as possible along each branch before backtracking. In the context of an island hopping problem, we can use DFS to traverse the grid and find all connected islands.

Here's how it works: we start at a given node (in this case, the top-left corner of the grid) and explore its neighbors. If we encounter a neighboring node that has not been visited before, we add it to our list of unvisited nodes and continue exploring its neighbors. We repeat this process until all nodes in the graph have been visited.

To implement DFS for island hopping, we need to keep track of two data structures: `explored` and `size`. The `explored` set contains all the nodes that have been visited during our traversal, while the `size` variable keeps track of the total size of the current island.

**Finding the Minimum Island Size**

Once we've implemented DFS for finding the minimum island size, we need to find a way to minimize this value. This can be done by initializing our `min_size` variable to positive infinity and then updating it whenever we encounter an island with a smaller size.

Here's how it works: as we traverse each island, we check if its size is less than the current minimum size. If it is, we update the `min_size` variable with this new value. This ensures that at the end of our traversal, `min_size` will contain the smallest possible island size.

**Practical Implementation**

To implement these algorithms in practice, we need to translate them into code. Here's an example implementation using Python:

```python

def minIsland(grid):

if not grid:

return 0

rows, cols = len(grid), len(grid[0])

directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

visited = [[False for _ in range(cols)] for _ in range(rows)]

def dfs(r, c):

size = 0

stack = [(r, c)]

while stack:

x, y = stack.pop()

if not visited[x][y] and grid[x][y] != -1:

visited[x][y] = True

size += 1

for dr, dc in directions:

r_, c_ = x + dr * rows + c + dc

stack.append((r_, c_))

return size

min_size = float('inf')

for r in range(rows):

for c in range(cols):

if grid[r][c] != -1 and not visited[r][c]:

island_size = dfs(r, c)

if island_size > 0:

min_size = min(min_size, island_size)

return max(0, min_size)

```

This implementation uses a nested DFS function to explore each island in the grid. It keeps track of visited nodes using a `visited` matrix and updates the `min_size` variable whenever it encounters an island with a smaller size.

**Conclusion**

In this article, we explored the world of graphs and one specific problem that requires graph theory: finding the minimum size of an island in a given grid. We discussed the basics of graph theory, including how to represent graphs using adjacency matrices or lists, and introduced the concept of depth-first search (DFS) algorithms.

We also developed an implementation for the minIsland function, which uses DFS to traverse each island in the grid and finds the minimum size. This problem is a classic example of how graph theory can be applied to solve real-world problems.

"WEBVTTKind: captionsLanguage: enThis course will help you learn what you needto implement graph algorithms and use themto solve coding challenges. Alvin's dynamicprogramming course is one of the most popularcourses on our channel. And now he's backto teach you graph algorithms. Hey, programmers,I'm Alvin from Structy. Welcome to our courseon graphs. And in particular, this is goingto be about graphs for your technical interviews.Of course, graphs are a very common topicwhen it comes to those technical interviews.And in particular, what I want to emphasizethroughout this course, is the handful ofpatterns that come up time and time again,on those technical interviews. in just abouttwo and a half hours, I'm going to give youall the tools you need to basically coverI'd say about 80% of all graph problems. Andso what I have in store for this course, well,I think the key to victory for your data structuresand algorithms, and especially your graphsis to visualize things, right. So we're goingto do is trace through a lot of differentalgorithms, and be sure to understand themat a high level. And that means going throughdifferent animations here, I think graphshave a pretty bad rap for being a difficulttopic. Because to a beginner, you can havevery, very different narratives around a problem,and not really understand. They're all reallybased on a graph premise. So we're going torealize that a bunch of different things canbe understood as graphs. So when it comesto the prerequisites of this course, I'm goingto assume that you know nothing about graphs.But you do know how to code, right, so I'mgoing to have the expectation that you understandsome recursion. So as you work through thecourse, and learn about different graph patterns,we're going to use those patterns to solvesome very classic interview problems aboutgraphs, right. And I'm going to give you plentyof opportunity to practice these patternsin different problems that we will be readywhenever you have them on a technical interview.What I love about the topic of graphs is justusing a handful of different algorithms, youcan cover the majority of graph problems,right. For every graph problem that we cover,we're going to split it up into two sections,section one is going to be about the approachfor the video. So we're going to go over thestrategy and overall theory, and be sure tosketch out a nice meaningful picture. We'realso going to talk about the complexity ofthe algorithm in the approach video. Followingevery approach, we're also going to implementthe code of course, I'm going to be writingall of my code in JavaScript, you'll be ableto follow along in any language that you like.So that means occasionally I'll be switchingto my code editor where you of course canfollow along. We're also going to be sureprovide links in description as well as linkson screen. That way you can formerly you readthe prompts for every problem, as well aslook at the different test cases. Alright,I think that's enough introduction. For now,let's hop right into the course. Alright,programmers. So let's jump right into thecourse, I want to start by giving you somebackground about your graphs, we're goingto go over the graph basics that you needto start attacking problems in a technicalinterview. So first off, what is a graph?A graph is really just a collection of nodesand edges. So with respect to nodes, you canvisualize them as typically just some circleswith some data inside of them. So I'll putsome letter values in my nodes over here.And when we refer to edges, that would bejust any connections between nodes. So forexample, if there was a connection betweenA and C, it would look something like this,right? What I can formally say is there'san edge between A and C, I can create manyedges between any nodes I want within thisgraph. Another word you might hear out inthe wild when it comes to describing nodes,as you might hear the word vertex being used,right, they're really the same thing. In thiscourse, I'll stick to the word node. And anedge is just a connection between a pair ofnodes. And that's really all a graph is ata high level, where things get interestingis how we can use this graph framework toactually solve a problem, right. So if youthink of these nodes as just things and theedges as relationships, a graph is grid describingthe relationship between things. For example,we can say that the nodes here are citiesand edges would be roads connecting citiesare in a similar way, maybe our nodes hereare courses, and then the edges representprerequisites. And so in the future, we'regoing to use graphs as a way to illustrateand frame some narrative problem. Let's talkabout this graph. In particular, here, I reallyhave drawn a directed graph. And that's becauseI have some arrowheads along the edges. Thatwould be a comparison to an undirected graph.So here, I have really the same structure,except I don't have any arrowheads on theedges here. And that means that there is nodirectionality to it right. If I look at thedirected graph, let's say I was at the nodeA, well, then I can travel to B or C, let'ssay I move to C. However, once I'm at C, Icannot travel to a, I can only travel to E,right? That's because I have to obey the directionof the arrow heads here. By take a look atmy undirected graph, let's say I was currentlysituated at the scene over here, that I dohave the option of traveling to either a orE, right? So if I traveled to a, that's allgood, I can even travel back to C. So thinkof as an undirected graph as a two way street.For now we'll just continue on with our directedversion. Let me also introduce some usefulterminology we can use when talking aboutthe nodes in our graph. If I was currentlysituated at this a node, I can refer to Band C as neighbor nodes. Alright, so a neighbornode is really any know that's accessiblethrough an edge, of course, obeying the directionof the edge. In other words, if I was currentlysituated at the sea node, that I only haveone neighbor of E, right, if I'm at the sea,you know, then I won't consider a neighbor.Awesome. When you visualize graph algorithms,you should really sketch a picture that looksjust like this, right literally drop nodesas circles and arrows as your edges here.However, when it comes to how we implementthis algorithm in some code, we're gonna haveto represent it in a more programmatic way.Right? So in my brain, I think of this imageof like nodes and arrows between them. However,in my program, I'm going to use typicallyan adjacency list, it's probably our preferredway to represent and graph information, right.So depending on the programming language ofchoice we're going to use typically, we woulduse some hash map data structure to representan adjacency list. Really, we're looking forwardto using some constant time, I'll look updata structure that has a key value pair mapping,right. So if you're in JavaScript, they'llbe an object, if you're in Python, they'llbe a dictionary. If you're in a language likeJava, or C, you'll be using an unordered map.Looking at this hash map, I have drawn orthis adjacency list, the keys of this adjacencylist are going to be every node in my graph,right, so I just have all of the node valuesA through F laid out as the keys. However,if you look at the corresponding values, thevalues are actually going to be an array,right? So if I look at this very first entry,it says that I have a node of a and then inthe array of populated all of the neighborshave a that is a has two neighbors have BNC.That's why I have this correspondence withinmy adjacency list. That holds true for everyentry within my adjacency lists. So for example,let's say look at the entry for e. So I goto the spot and make j c list where the keyis E, it only has a one outgoing edge to be.That's why the array for he only has be insideof it. One thing to also note is even if anode has no neighbors, it should still appearas a key within my adjacency list. For example,if you look at the D, node D has no outgoingedges. That's why its neighbor array is empty.However, it should still at least appear asa key within my adjacency lists, right, thatway, you can still know that the D node exists.So at the start of the course, will usuallybe taking in adjacency list as the informationto represent a graph, right. But as we sketchthrough things on the whiteboard, we shouldbe visualizing them using a nice picture likethis. Awesome. So let's actually jump intoour first pair of algorithms. To me, the mustknow algorithm for a graph is really goingto be to do some sort of traversal on it.Why don't we start by talking about a depthfirst traversal, something you may have heardof before, right, now we're going to talkabout the depth first traversal algorithmthat operates on a graph. So let's start byunderstanding at a high level what order adepth first traversal would give you. So let'ssay I had some starting node, and I'm gonnachoose a as my starting node, right, so I'mgonna color it here in yellow. If I was followinga depth first traversal. Now that I've, youknow, chosen as my starting point, I can eitherhit B or C. Next, I'm just gonna commit tousing B. So let's say I had the sequence sofar have a comma b. And at this point, ifI was truly following a depth first traversal,I must go deeper to the D node. In other words,I don't go to the C node yet. Cool, that wouldbe a true depth first traversal, right. Atthis point, now that I've bottomed out atD, D is a dead end, right? I can't travelto F from D, because that would be disobeyingthe arrowhead. And so now I can move to thatother neighbor of C. And from here, the algorithmwould continue, right, I go from C to E, andthen e to B. And technically, I would haveto double traverse some nodes like B and Dover here. So overall, in this yellow coloring,I have colored the full region that a depthfirst traversal would explore starting ata notice that if you started at a it wouldbe impossible to reach F. And that's kindof normal, right? That's kind of why we usethese traversal algorithms that can tell youwhether or not you can travel between somenodes. And we'll see that literal problemlater on. Right? So you're probably wondering,you know, exactly how do we implement this,but for now, I just want to stay focused onthe order that we got, right. So just regardingour depth first traversal, we remember thefirst three iterations of the algorithm, wehit the sequence of a B, D, right, that'sindicative of a depth first traversal. Nowlet's compare that to the breadth first Marion.So I'm going to lay down the same exact graph,we're also going to start a traversal at thea node, but this time follow a breadth firstorder. So I have a first and let's say, youknow, I chose B as my next node when it comesto breadth first traversal. It doesn't matterlike which, you know, initial neighbor youchoose, so I'm just gonna choose B. But nowthat I've chosen B, if I was following a truebreadth first traversal, I must hit c next,right. And that's the main difference betweenour depth first and breadth first reversalsfor the same graph, my depth first would starta B, D, whereas my breadth first would starta, b, c. And so you're probably wondering,is there any importance between this nuanceright? When would I prefer depth first overbreadth first, or vice versa? Either a depthfirst or breadth first traversal would explorethe same exact nodes within a graph. However,it would explore them in a different order,right? And this is more obvious to see whenwe have a larger graph with way more edges.And so let's look at how he depth first traversalexplores again, but this time on a much largergraph, let's take a look at this one. So I'mgoing to choose some random node as a startingpoint, let's say I chose this node in yellow,that was doing a depth first traversal, whatI'm going to do is, you know, pick a directionand travel in that same direction as far aspossible before switching directions. So let'ssay I move to the right, at this point, Iwould have to continue moving toward the right,until I can't move to the right any longer,at which point, I have to choose some newdirections, let's say it was downward. I'llkeep doing that until I can't move downwardanymore. And so I'd have to move to the leftnow, now I'd keep chasing this single pathin a very deep direction. So that's behaviorindicative of a depth first traversal, right,you're exploring one direction as far as possiblebefore switching directions. Let's comparethat to a breadth first traversal. So let'ssay start at the same node in pink, if I wasfollowing a breadth first traversal, it wouldlook something like this. From the startingpoint, I would explore all of the immediateneighbors of this node, kind of in a circlelike this. Now I just keep applying that behavior.So as you notice about the breadth first traversal,is it'll tend to explore you know, all directionsevenly, right, instead of just favoring OneDirection all the way through. That's reallythe only difference between a depth firstand breadth first traversal. Later on thecourse, I'll bring up explicit problems whereyou might prefer one over the other. All right,but for now, what I want to do is give youall the background you need. So you can actuallybuild this algorithm will kind of talk aboutthings at a high level, consider this thepseudocode, then, of course, we'll expressit in some JavaScript code later on. So whenit comes to actually implementing in code,these two algorithms, the key is to understandthat a depth first traversal uses a stack,and a breadth first traversal uses a queue,recall that a stack is something where youadd to the top and remove from the top aswell, or is it Q is something where you addto the back and remove from the front, andit gives you two very different orderings.That's really the only difference betweenthese two algorithms. So let's start by tracingthrough our depth first traversal, of course,using a stack, so I'm going to use a slightlydifferent graph. And to visualize my stack,I'm going to use this bar to represent thebottom of my stack, obviously, for me, atleast I think of a stack as some verticaldata structure. Cool. So let's say I justarbitrarily chose a as my starting node toperform my depth first traversal, right, inthe long run, just want to print out all differentnode values within this graph. So what I'mgonna do is I'm gonna take my starting nodeof a, and I'm just gonna immediately initializeit onto my stack. So right now as the onlything on my stack, it's also at the top ofmy stack. And now I can enter the flow ofthe main algorithm here, because I have astack, what I can only do is remove the topof my stack. So that means I pop off a fromthe stack, and consider the a node, my currentnode being looked at, right? At this point,let's say I print out a to my console. Andfrom here, what I want to do is consider A'sneighbors, right. So if I look at the C node,what I should do is just push c to the stack,then also push B to the stack, right. Andit doesn't matter like in which order youpush these neighbors. If I want it to hitB first, then I'm going to push them second,right? Awesome. That would end like my firstiteration of this depth first traversal. Cool.So at this point, I can look at my stack,and my stack still has some data on it. SoI should do is again, pop the top of my stack.So I'm going to pop and be off my stack. Andthat becomes my current, I'm also going toprint it out. At this point, I look at B'sneighbors, B has one neighbor of D and soI push d to the top of the stack. Notice thatbecause I have a stack D ends up on top ofthe C, right. And so now when I get to anotheriteration, when I pop the top of my stack,I look at the D node as my current, right,and I can print out D. And this feels goodbecause so far, my print order would be aBD, notice that I kind of pursued that singlepath deeply following a BD. But I have tolook at DS neighbors, I can take f and justpush f to the top of my stack. next iteration,my stack is still on empty. So I should dois pop the top F is now my current, I canprint out F, but f has no neighbors. So Fisn't going to push anything else to the topof the stack. Right? At this point, I getto this next pass, and I pop the top of mystack. And that means C is now my current,I can print out CS value. And then I can lookat Sue's neighbors. And I just push e to thetop of my stack. On this last iteration, Ipopped up on my stack, he is now my currentI print out he since he has no neighbors,I don't push anything else to the top of mystack. And at this point, I've reached thestate where my stack is empty. And that meansmy algorithm is done right that means youexplored as far as possible within your graph.Notice that it might not necessarily be thecase that you're able to hit every node ofthe graph. And this particular example itwas possible though, awesome. So let's redothat trace using Our breadth first algorithm,which means we just adjust things slightly.And we use a queue order. Remember that aqueue is a first in first out data structure,meaning things enter to the back, and thenthey leave from the front. And so let's sayI use this arrow to represent the directionalityof my queue, right. And I start the algorithmin the same way for my breadth first traversal.Let's say I want it to begin at node A. SoI just initialize my queue with a cool, soI start by removing the front of my queue.So a becomes my current node, I can printout a as well. And now I consider A's neighbors,right. So I consider B and C. If I wantedto travel to B before C, then I should pushB to my queue first, right, so I add B tothe back of my queue, right. And I shouldalso add c to the back of my queue, right.And that would actually end my first iteration.So now I look at my queue still has some stuffon it. So I removed the front of my queue,that means B becomes my current. Of course,I print out B. Now I consider B's neighbors.So I just look at the D node, and I push dto the back of the queue, since D enters throughthe back and ends up behind the C, and that'sreally important behavior. next iteration,I removed the front of my queue. So my currentis now see, right, I can print out see, andthen look at sees neighbors of just E andI add e to the back of the queue, which meansthat in the order of my queue, he ends upbehind the my next iteration, I removed Dfrom the queue, and I print out the editsneighbor of F to the back of my queue. nextiteration, I removed e from the front of myqueue, print it out. Since he has no neighbors,he is not going to add anything else to theback of the queue. And of course, finally,f leaves the front of my queue, I print outF, F has no neighbors, at which point nowmy queue is totally empty. And since our queueis empty, that would be the end of our algorithm.Alright, and that's all there is to our depthfirst and breadth first algorithms, they'regoing to be the nice baseline code that weuse to solve many different graph problems.I think that's enough theory. For now, whatI want to do is now switch to my code editor,where you can actually implement these inJavaScript, hey, programmers, here I am inmy editor, what I want to do is now show youhow to implement those depth first and breadthfirst algorithms. So we'll start with thedepth first. And my goal is really just tobuild a function that will print out all ofmy values in the graph, according to a depthfirst traversal, right, we're going to definethis function depth first print, making anarrow function in JavaScript, it's going totake in the graph, which is going to be givenas a nice adjacency list. And this is actuallythe same graph. Now last example we tracedout, I'm also going to need to specify somestarting node here, I'll call it a sourcenode, we're going to begin the traversal.Starting at that node. Cool. And so we knowinherent to a depth first traversal is goingto be a stack. So I'll show you how to implementthis iteratively, which means you need anexplicit stack. For me in JavaScript, that'sas simple as just using a JavaScript array,right? I'll make it empty at the start. AndI can use this array as a stack, if I justcommit to using operations that manipulatethe same end of the array. In other words,if I just use push and pop, that will alwaysmanipulate the end of the array, right? removingand adding to the end of that array. WhatI want to actually be sure to do is I wantto initialize the stack with my starting node,that is with my source node. Remember thatlike a node here is really just designatedby some character. Cool. And when it comesto designing like the main loop for the algorithmhere, do you want to keep running the algorithmwhile the stack is not empty? In other words,wall stack dot length is bigger than zero,that I have to keep running. That's very reminiscentto what we expressed on the whiteboard. Sowhen it comes to performing like a singleiteration of this depth first, what I wantto do is remove the top of my stack. So ifI do stack dot pop, that will remove the lastitem of an array, in this case like the topof my stack, and also return it to me. SoI'm going to save that to a variable, I'llcall it my current. And so this point wouldactually be a great opportunity to just printout that current. So I'll console dot logcurrent, right? So looking at, you know, thisexample over here, since I initialize a stackto contain just the source note of a, on thevery first iteration, this while loop, I wouldof course, pop out a, then I would print itout, right. And from that point, what I wantto do is consider A's neighbors of B and C.So if I want to look at like the array associatedwith a, I can just key into my graph, right,cuz my graph is an object right now. So ifI say graph, square bracket, current, right,if current is a, that means graph, squarebracket current would give me back this array.I want to iterate through every node or everyneighbor in that array. So I'm going to nesta loop here. And I say for let neighbor ofthat array. So if you're familiar in JavaScript,if you just use a for of loop, they'll iteratean order through an array. So now I'm hittinga neighbor as B and neighbors see. What Iwant to do with those neighbors is simplyPush them to the top of my stack. So thatwill just be stacked up, push and push thisneighbor. Awesome, I'm going to be sure topush every single neighbor that has. So sometimesI'll have two neighbors. Other times I'llhave one neighbor, or even no neighbors. That'sreally all there is to implementing a nicebaseline depth first print. Something thatI do want to point out, my favorite way toimplement this algorithm is to consider likeprocessing your node, when it leaves the stack,not when it enters the stack. In other words,I usually write like my print statement, rightafter something is popped. And the thing thatI pop is exactly what I print. Right. So let'sgo ahead and give this a run, see what weget. It looks like in my terminal, I got theorder of AC e b df, which you'll notice isslightly different from what I expected fromover here. However, this would be also a validdepth first traversal, we have to bear inmind is you know, depending on like the arbitraryorder of values within the same neighbor'sarray, you could tend a different directionat first, right? Most important thing I lookfor when it comes to verifying a depth firstis to make sure that I you know, chase thesame direction before switching directions,right. So since I started out with a C, soI go a and then to a C over here, the nextmove would be going to E and that's exactlywhat happened in my code, right. And thenonce I hit E is actually a dead end. So thenI can go on to my other lateral neighbor likeB, right. And so I can contrive the same orderexpected here, if I just flipped this right.And so I put c followed by B. I'll give thataround. They're both valid. depth first traversals.See what we got now. Cool, now I get the exactorder of A, B, D, F, C. And really think aboutwhy that is, right. So let's say that I justpopped out a from my stack. So I printed outa that's nothing fancy, right. And then fromthere, I start iterating through the arraythat's associated with a right, so on thefirst iteration, I iterate through C, right?If I push C on the stack, let's say this isthe bottom my stack, by pushing on the stack,it's right here. Then followed by that I pushedB on the stack. Now B is on top. Since B ison top, I know like the next top level iteration,this while loop, I would remove B and that'sgoing to be the next note I visit. And sothey're really both depth for sure Russell's.Nice. So two things to note, you're definitelygoing to use a stack to implement depth reversal.And you can use the stack in a few differentways. Right? So here I'm using like an explicitlike array as a stack. And I'm implementingthis using some iterative code, right. Sousing a few loops, right, what you can alsodo is implement depth first recursively, becauseI know any recursion uses the underlying callstack. So let me show you how to implementthat as well. And when it comes to, you know,having all these different tools in your arsenal,I would definitely practice both the iterativeand recursive flavors. We'll see that lateron in this course. So let's say I wanted tosolve the same problem. But now recursively,it's actually going to be less code. So I'mgoing to have the same sort of arguments,I'm going to have the graph which is the adjacencylist as well as a source node, consider likethe source node as like your current location.So if I'm at some node, maybe the first thingI should do is just print out myself, right,print out this node, so I'll do is consoledot log, this source node. And that feelsgood just from the get because when we actuallydo a top level call to this recursive function,they're passing in a as the source node. SoI do want to begin a as a first note in myprint, and then from there, I need to lookat AES neighbors. Well, if you want to lookat as neighbors like before, just key intothe graph, adjacency list using that node,right, and this would give me an array ofCNB. Now I just iterate through that array.So I'll say for let neighbor of that array.And at this point, what I want to do is nowdo the recursion, right, so I make a recursivecall on each of these neighbors. So for me,that means just called depth first print,you give the same graph, right, the graphobject doesn't change, but you should changelike the source node. Now you want to passin that neighbor as the source node. And you'regoing to make a recursive call for every neighborin that array. And this would actually beall we need. Let's go ahead and just run thisversion. divider run over here. Looks likenow we get the order AC E, B, D, F. And that'sreally again, another type of depth firstprint, right, not exactly this order, becausethis time we chased c first, right, we wenta C, I want to get exactly this ordering andmy recursion, then I would have to put inB first, really same sort of pattern. Nowlet's get that into the run. Good AB de FC.One thing I want to bring up about this recursivefirst is it has no explicit base case, meaningthere's no obvious like, if statement thatjust like returns like you'd typically seein most recursion. That's because in thisproblem I have an implicit base case whena node like he is a dead end. All right, let'ssay my current source coming in is he, well,then when I iterate in this for loop, I'miterating through this empty array, I meanto have zero iterations. If you have zeroiterations, then you never make a recursivecall. Right? That's the same thing as havinga base case, right? A base case is reallyjust a scenario where we don't have a recursivecall. So that's how this code still works.Alright, so now you know how to implementdepth first in two ways, right, iterated andrecursively. And they both use definitelya stack. Let me now show you how to implementyour breadth first, right as well commentout some of this code. Now we'll do a nicebreath first, give myself some room over here.So for a breadth first, we want to solve theswan iteratively. And it's really only possibleiteratively, right. So I know a breadth firsttraversal demands a queue, if you try to likeimplement a breadth first traversal usingsome recursion, and under the hood, there'ssome stack data structure, that's going tofight against the queue order that you want,right? So for breadth first traversal, you'realways typically going to be writing someiterative code. So some loops, right? Letme define this, I'll say breadth first print,take in the full graph, adjacency list, aswell as the source node, I want to initializemy queue. With that source note, again, thequeue here is just going to be an array inJavaScript. So I'll say const q equals anarray that begins with just the source node.Awesome. And I'm going to use this queue byjust committing to two specific methods onmy arrays in JavaScript. So if I use arraydot shift that removes the first element ofan array. If I do array dot push that addsto the last position of an Array. And usingthose two methods in combination would giveme a nice cue, right, add to one end and removefrom the other end. So like before, we'regonna have a while loop, we're gonna iteratewhile our queue is not empty. And so whilequeue dot length is bigger than zero, nice.And same thing as our iterative, you know,at first, you want to start by just removingthe front of your queue. So I'll say q dotshift, that will remove the first elementas well as return it to me. So I can savein a variable, I like to call it current,just like the whiteboard, right? And fromthere, maybe I'll print it out. So consoledot log, this current node. And from here,just consider your neighbors, right. So ifI key into my graph, using this current node,that gives me an array of its neighbors, Iwant to loop through each of those neighbors.So I can say four will say let neighbor ofthat array. And for that neighbor, I wantto add them to the back of my queue. So forme, that would mean simply q dot push, I'mgoing to go ahead and push that neighbor.Awesome. So I remove from the front, and Iadd to the back. So that looks pretty good.Let's go ahead and give it a run. And actually,before I do that, I'm going to change theorder of this, put the CNB. Again, doesn'treally matter the relative order for neighbors,I just want this exact output, and we'll talkabout why that is right. Give that a run.So I get ACB EDF just like I expected ACBEDF, right. So let's say you're on the firstiteration of this breadth first print, I knowthat I would have just removed a because Iinitialized a on the queue, right? So my currentis a and I print out a and then from there,I start iterating through this array, right.So on the first iteration, I have C, thatmeans I put c into my queue, right? And thenafterwards, I put B, if you put C and thenB, that means C is at the front of the queue,which is why on the second iteration, I haveC first, right? So that's how you can manipulatepotentially the lateral order of a breadthfirst print. Awesome. That's all there isto this traversal algorithm, what I reallywant emphasizes, especially if you look atthe apples to apples iterative code, you comparedepth first or breadth first, it's almostidentical code. You're really just changinghow you access items in your array, right?You either pop or push or you shift and pushharder than that the whole like structureof this code is identical, right? All right.So that's our introduction on depth firstand breadth first for our graphs. In the nextsection, we're going to start to solve a problem,right, which will be really fun. I'm justutilizing this code as our baseline tool.And then that section also promised that startdoing the analysis for bego of these algorithms.So let's jump back to that whiteboard. Hey,programmers, welcome back, right, and let'sgo over the approach for this has path problem.So in this problem, we're gonna take in anadjacency list representing a graph for thisproblem, and really all graph problems, youdefinitely want to visualize this one witha picture. And so what we'll do is we'll interpreteach key of this adjacency list as representinga distinct node. And if I look at any particularlist, I can see that this f node should pointto G and I. And they do tell us in this problemthat I have a directed graph. So I'm goingto draw arrowheads on these edges here. SoF points to G, as well as f points tie. AndI'll create similar edges based on the informationin the given graph. So we end up with an imagelike this, until they tell us that this isa directed graph that explains the arrowheads,but they also tell us that this graph is acyclic. So if you're unfamiliar, a cyclicjust means No cycles, that kind of begs thequestion, what is a cycle in a graph. So acycle would be a some path through nodes,where I can end up where I want started. Inother words, if I started at the a node overhere that I can go to B, then from there,I can go to C, then back to a, and so on andso forth. So if I did a traversal, on theSigma graph, I would get an infinite loop.And what they're saying is, our graph inputis guaranteed to be directed. So it has arrowheads,but also a cyclic, so we don't have to considerany infinite cycles here. That being said,In this problem, we also want to take in notonly the graph information, but also a sourceand destination node, we want to do is returntrue or false indicating whether or not wecan travel from the source node to the destinationnode. In other words, is there a path thatexists between those two nodes? For this problem,you can use either a depth first or breadthfirst search to actually solve the problemhere, I'll trace through in this approachvideo, just the depth first search. But inthe walkthrough, I'll be sure to code it upboth ways. So let's say started at my sourcenode, I know that if I was doing a depth firsttraversal, I can either choose the IRG, let'ssay happen to choose to G next. Now I haveno choice, right? If I'm doing truly a depthfirst, I should go deeper to the H. So thenI hit this H. And as I traverse through thesedifferent nodes, I need to ask myself if mycurrent node is equal to my destination. Sofar, that hasn't been true. At this point,I bottomed out with my h node, I can't travelany deeper. So now I can move laterally toa node like I, at this point from I can eithermove to a K or a G, let's say by luck, I justhappen to go to the G, this would actuallybring me down a path I've explored previously,which we can optimize later on, but wouldn'tbe too much of a big deal. Eventually, ifI continued this depth first search throughthe graph, I would end up at a node that matchesmy destination, at which point I can returntrue signifying that there must be some pathfrom F to k, just doing a depth first search.And as we do this depth first search, it'sreally important that you obey the directionsof your arrows. So I should never try to travelupstream. So that was a scenario where wewere able to find a path from source of destination.That's why we return true. Let's reset andsay that now, I should return false. Alright,so let's say my source was J. So I start atJ. And I'm trying to get to my destinationof F. If I start a depth first traversal,here, sorry, my j node traveled to the AInode. At this point, I can hit either theG, okay, let's say I happen to hit the k,this point of bottom now. So now I can moveto the G. And then from there to the H. Andat this point, there's actually nowhere elseI can go, right. So if I finish my traversalthrough the graph, using either a depth firstor breadth first and I never hit my destination,then I can just return false, right? It mustbe the case that there is no such path frommy source to my destination. When it comesto implementing the depth first and breadthfirst reversals on this graph, it's goingto be exactly what we're used to, you caneither use a stack and solve it recursively.Or you can do it iteratively. And use a queuein which case you'd be doing the breadth firsttraversal. We talked about the complexityof this, let's say that n is the number ofnodes of our graph, a common thing that youcan also do with these graph problems is definee as the number of edges here and edges refersto a connection between two nodes, basicallyjust the arrows. So if we use these two termsof number nodes and number edges, we wouldhave a time complexity of our V o of the numberof edges as because we would have to travelthrough every single edge of our graph. Here,the space complexity would be based on thenumber of nodes, right? If I solved it, recursively,or even iteratively, with some sort of a depthfirst stack, then the worst case, I wouldhave to have every single node on the stack,right? Likewise, if I saw the eternity witha breadth first I would have every singlenode on the queue. So that's just one waywe can define the terms for analyzing thetime and space of this graph. Typically, forgraph problems, another acceptable way toanalyze the time and space of your algorithmis to just use a single variable and justdefine n as the number of nodes. That's becauseif you say n is the number of nodes, thenwe can also say that n squared would be thenumber of edges, or that big O. It's aboutthe worst case. So let's imagine the worstcase graph. Let's say I just had these nodesof ABC. Well, if I wanted to create as manyedges as possible, how would I just createa single edge? Well, an edge is just a connectionbetween two nodes. So you could just reallydraw an edge for every pair of nodes in yourgraph, something like this. And that's whywe can say that n squared is the number ofedges of any particular graph. And so if youjust wanted to use n to define the complexityhere, then you could say that your time isgoing to be O of n squared, and your spacecomplexity would still be O of n. Do knowthat these are both two valid ways for definingthe complexity for a very typical graph problems.That being said, I think this is pretty straightforward.Let's hop into the walkthrough video whilewe're actually implement both a depth firstand breadth first solution for these. I'llsee you there. Hey, programmers, Alvin here,right now. Let's go over Ah, JavaScript solutionfor this has path problem. And so we'll jumpright in, we're gonna start by solving thisone using a depth first traversal, which Iknow requires some underlying stack data structure,I'll just implement that using recursion.So I can leverage the call stack to get myordering. And so I'm gonna solve this recursively,I'm gonna consider my source argument as likemy current position during the traversal.And so I can have a base case in check. Allright, if my source is equal to my destination,that I must have found the thing I'm lookingfor. So just return true. This base case signifiesthat I found my destination. So there mustexist a path. And so I return true, alwayspaying attention to the type that they wantus to return for this function. Let's sayit's not true, well, they need to keep looking.So what I should do is consider my currentnode, which is source, consider its neighbors.If I key into my adjacency list, I know thatthis is going to be an object. So I key intoit using my source, that would give me anarray of all of its neighbors. So for example,let's say it was staring at this one, if mycurrent source was F, and I say graph squarebracket, F, I would get back an array of gi.So now I want to look through the neighbors,right? So I can see over here is turned usinto a loop and say for that neighbor of thoseneighbors, I want to traverse to them, whichmeans I call recursively. Right call has path,keep your graph the same, but update yourcurrent position. Now I'm going to be situatedat the neighbor. And the destination staysthe same, right, always have the same goalto get to solving this one recursively. Sothink about what type of this is going toreturn, I know it's going to give back Boolean,right, it's going to tell me whether or notthere is some path between my neighbor andthe destination, right. So if there's someconnecting point, or some connecting pathbetween my neighbor and the destination, thenI know that there must be some path from mysource to the destination, because your sourceis definitely next to your neighbor, right.So there would be a path between all of us.And so what I'll do is, check if this recursivecall returns true, I'll make it explicit here,maybe it's clear. And so if there is somepath through my neighbor to the destination,then I can return true, just pass that trueupward. Because once I find a path, you canjust exit out and return that shoe all theway back to the top level of color. But let'ssay that this call returned false, that meansthat there is no path through my neighborto the destination. But it couldn't be thecase that some other neighbor is actuallygoing to work out. And so what I don't wantto do is just say like else return false,you should be able to immediately catch thatcode like this as suspect because there'sno point of having a for loop then right?If in either case, you're always going toreturn, then you're never going to have asecond iteration of this for loop, right?So if I don't find a path through my neighbor,so if this call returns false, then that'sokay. Just continue on to the next iteration,and search through your other neighbor. thatbegs the question, Where should we returnfalse, needs to be after the for loop? Soonly after I searched through all of my neighbors,and I never find a winning path? Should Ireturn false, and that'd be our nice depthfirst traversal. Let's give that a test run.Awesome. There we have it. One thing to bearin mind here, we are leveraging the assumptionsin the problem, right, they tell us straightup that the graph is going to be given isa sick like, so there are no cycles. So that'swhy in our code, we didn't really worry aboutgetting trapped in an infinite loop. In ourupcoming problems, we'll have harder grassto actually deal with that sick case. Butfor now, this is a good baseline solution.While we're here, let's also do a referencesolution, which you know, by now should beiterated, right, there's no way to do likea breadth first recursively. And so I needto create my own queue. So I can create aqueue, kind of in a pinch, I always just usean array in JavaScript, I'm gonna initializethat queue with my source on it. So I'm gonnarefer to like source and destination, they'rereally nodes. But in the context of like ourproblem, they're really just given us strings,but they represent nodes, right? So thinkabout the information they represent. I'mgoing to iterate while my queue is not empty.So while q dot length is bigger than zero,should be familiar code, very similar to ourtree algorithms. And I start a single iterationof reference by removing the front of my queue.So I can say q dot shift some of the front,I can call that my current node that I'm traversingthrough. And now that something has left thequeue, typically here is where I check, Ican check. All right, if a thing I just visited,if that is my destination, then I can justreturn true, right, I found the thing I'mlooking for. So there must be a path thatconnects my original source and my destination.Nice. But let's say this was not true. Well,then I need to consider its neighbors. Solike before, look at the neighbors just keyinto your graph using the source like it'sa graph, square bracket source. That givesme an array of all of the neighbors, all theneighbor nodes. That's what I want to do hereis iterate through every neighbor Over there.And then I can just add them into my queue.So q dot push that single neighbor, and dobe sure to implement your true breadth first.So you need to make things leave from oneend of your queue, and you add to the otherend. So this codes looking good. So you shouldrealize how similar This is to our old likebinary tree breadth first, except now we haveto account for the fact that we could havelike a dynamic amount of neighbors here, notjust dot left and dot, right. So I'm justiterating through all those neighbors addingthem, I need to wait to return false. Andyou guessed it, the move is after you finishthis entire while loop, if your cube becomesempty, then you must have explored as faras you could. And if you never return true,and now you can return false, because it mustbe the case that there is no path betweenthe original source and your target. So let'sgive this a test run will have a very similartime and space complexity. But this wouldbe the code for all of my iterative fans.So here I'm getting a little error. Let'ssee what we did wrong here. So it looks likeI timed out here. Let's see bug this one together,I had to guess that means I did somethingwrong getting trapped in an infinite loop.This condition looks okay, right q dot lengthgreater than zero. And so here it is, mustbe the case that I'm not correctly iteratingthrough the neighbors here, I just wrote source.Instead, I need to say current, because nowI'm doing this iteratively, right. So whatevernode has just left my queue, I consider thatnodes neighbors and add them to be visitednext through my queue. So let's give thata test run. honest mistake there. Cool. Andthere's our breadth first solution for thishas path problem. So what I want you to dois practice both the depth first and the breadthfirst, like you expect, we're going to doa lot of graph problems coming up. And dependingon you know what the problem is asking sometimeswill prefer one type of algorithm over theother. So it's really important that you practiceboth of these algorithms. Now, all the problemsare relatively easy. So practice this, giveit a shot on your own. And I'll catch youin the next problem. See you there. Hey, programmers,Alvin here, right. Now let's go over the approachfor this undirected path problem. So we'lljump right in. In this problem, we're goingto be given an edge list for a undirectedgraph. So if I are familiar with the terminologyhere, really what we're saying is every pairand this edge list represents a connectionbetween two nodes. For example, if I lookat the first edge, and the list, I see i commaj, that means that there's a edge or connectionbetween i and j. And since this is an undirectedgraph, not only can I directly travel fromi to j, but I can of course, move from j toi. So it really represents a connection inboth directions. And so as we start to attack,this problem we'll want to do is actuallyconvert this edulis into a more favorableformat, like an adjacency list. That's becausetypically, when we perform our traversal algorithms,they work best on an adjacency list form.So let's start by doing that conversion here.And I'll actually be pretty easy to code up.So I want to basically generate a graph whereI have nodes as keys, I want them to pointto a an array of their neighbors. For example,if I wanted to convert the first edge intoan adjacency list form, what I can do is createkeys for i and j. Now that I is a neighborof J, and also j is a neighbor of I, so I'mgoing to populate those neighbors respectively.Now just follow this process for another edge.So if I look at the edge, k comma i, I needto create a new key for K. And I'm going topopulate that with I and then for the existingkey of I, I just add k into that collection.So do bear in mind, the most important thingabout this conversion is because we know thatthe graph is going to be undirected, wheneveryou put a connection within your graph, makesure that you have the inverse connection.So if I have an edge from k to AI, they alsoneed to have information for it. Okay. Andthis process would just continue for the entirelist of edges. And by the end of this conversion,we'll end up with an adjacency list just likethis. And now we're ready to perform our mainalgorithm. When we go through the code walkthroughfor this, I'll show you in depth how you canactually create this adjacency list. And sowhen we want to actually come up with a traversalalgorithm to solve a graph problem, it reallyhelps if you actually visualize the shapeof your graph. So actually want to visualizethis in terms of nodes and edges. That meansa bunch of circles and lines between them.If you drew out a nice picture for this graphinformation, you would end up with a diagramlike so. And so we'll go through the restof this approach video just referencing thisdiagram. Something important I want to bringup at this point is for this graph, a verycommon case we'll have to handle is what ifyour graph has a cycle. And that's especiallytrue for your undirected graphs. And so justfor the purposes of this approach video, I'mgoing to add an additional edge just so wecan talk about an explicit cycle. So I'm goingto add one new edge from k to J. Cool. Thereason is now there's a nice big cycle oflength three highlighting in red right now.And this cycle is important to watch out forbecause if we don't do any special handlingThen we may get trapped in an infinite traversal.So imagine I started at this keynote, andnext I moved to J, then I would move to i,and then back to k, and then back to J, andthen I, and so on. So now it gives me a cycle,we'll have to guard against that. And so Ican have a cycle of three nodes here, right,and you can really have a cycle of basicallyalmost any size, as long as it's more thanone. So for example, if I took a look downhere, notice that my graph actually containstechnically like two separate islands, butwe would consider them as just one giant graph,right? So I've got the small island of O andN, they actually form a trivial cycle, right?If I started traversal, at o. From there,I can move to n. And because I know that theedge between o and n is bi directional writesan undirected graph, that means I can travelback to O, and then back to n. And this wouldgive me cyclic behavior. So have to watchout for all types of cycles in this problem.So in the context of this problem, not onlyare we given a graph, we're also going totake in a two nodes. So let's step throughan example where I want to return true orfalse, is there a path between I and L. SoI'm going to mark those in my graph Israel.So I'm going to start at the notify. And tosolve this one, you can use any type of traversal.So either depth first or breadth first, I'llstep through explicitly the depth first traversal.Right. Now, in order to avoid any infinitetraversals, I want to mark my nodes as visitedas I travel through them. So not only do Isituate myself at this source note of I, butI'm gonna mark it as visited. And you canimplement this like marking a visited pattern.And a few different ways. When we code thisup later on, we're probably going to use aset to represent what we have visited. Butfor now, I'll just check them off in my diagram.And so in my diagram, if you see a checkmarknext to a node, that means that I alreadyhave visited it. So since I'm at this nodeof I want to move to its neighbors, so I'mgonna move to the neighbor of J. And I'llalso be sure to check it off as visited. Atthis point, I can move to one of Jays neighbors,let's say I move to k. And I'm also goingto mark it as visited. Now then Matt K, Ican move to a few different neighbors, I couldeither move to I LRM. Let's say by chanceI chose I, I once I get to this, I know, I'mimmediately going to be able to see that,oh, I visited this node previously. So whatI should do is not travel through it again.Instead, I should go back to the K, right,because this eye node is already visited.And that's where I actually avoid the infiniteloop. So instead, I moved to some of Kay'sother neighbors, let's say I chose the L.At this point, I would mark it as visited.If I do a quick check, I can see that thisnote I'm at L is also my destination node.So I must have just found a path between mysource and the destination. So at this point,if I find my destination, I can just returntrue, which was a pattern we spoke about ina previous problem, the only additional criteriawe need is to mark nodes as visited. Thatway, we don't get trapped in an infinite loop.And that's only going to be needed if we havecycles in our graph, which if they don't giveus any assumptions we should always guardagainst. So let's take a look at another example.Let's say I had a source of K. And my destinationwas Oh, just looking visually in the graph,you can already see that there's no way toget from k to O, because they're disconnected,right, they're on separate islands both stepthrough the algorithm regardless, so I'm goingto start at K gonna mark it as visited, I'mgoing to visit some of Ks neighbors. So Ican move to i, then I can move to J. And thenat this point, I would move back to K andreally make sure they don't explore any ofKs visited neighbors, so I don't move backto I right, instead, I should move to an unvisitedneighbor, like l market is visited, then Ionly have one other node to visit, which wouldbe this m node. And at this point, I've actuallyexhausted this full graph region, right, there'snowhere else I can go. And once I finishedmy traversal, if I never find my destinationnode, then I can just return false, right?It must be the case that there is no paththat exists from my source node to the destinationnode. That's really all there is to this algorithm.Let's talk about the complexity. If we saythat n is a number of nodes, let's also definethat he is a number of edges. Like we saidpreviously, this is something typically acceptableto do for our graph problems. I know thatthe time complexity is going to be roughlyof the number of edges. And my space complexityis going to be O of n that is the number ofnodes. I think it's worth stepping through,you know what this complexity actually means,you know, big O refers to the worst case.So let's think about a worst case graph thatwe can have. And there are a few differentgraphs that you can kind of design and thinkof, I'll just show you one example. So let'ssay I was given a graph like this, right?Notice that although z is kind of on its ownisland, all of these nodes that is a threeas well as a C note. They're all members ofthe same graph. So let's say I wanted to figureout is there a path between A and z. So ifI did my traversal algorithm from here, I'llstart at a then I move to B, and then to C,and then to D, and then to E. At this point,I've covered all of the edges in the graph.Remember that the edges are the arrowheadshere, because I have to travel through everyedge of this graph. That's why we said thetime complexity in the worst case is goingto be o of E, right o of the number of edges.and here we can say the space complexity isO of n. Because if you're doing this witheither a depth first stack, or a breadth firstqueue, in the worst case, you would have toadd everything you visited, or that is allof the nodes onto your stack or queue. That'swhy we say for regular graph traversal algorithms,we have a time complexity of o v, and a spacecomplexity of O of n. All right, I think wehave the approach for this algorithm downpat. At this point, I want to join me in thewalkthrough videos, where we can actuallysee how to implement these visited patternsin some code. I'll see you there. Hey, programmers,Alan here, right. Now let's go over a JavaScriptsolution for this undirected path problem.So we'll jump right in, just like we said,in the approach video, there's going to bea two parter. First, we're going to convertour edge list into an adjacency list. Thatway, it's easier to do a classic traversalthrough it. So I'm going to pretend I hada helper function here. That gives me backan adjacency list. I'll call it graph. AndI'm going to call this helper function, we'llsay build graph. And if I pass it, just allof my edges, I want it to do that conversionfor me. So let's work on that helper functionright now. And then we'll jump back to undirectedpath. So I'll create my build graph function,just going to take in the edges, right. AndI know I want my adjacency list to be in theform of a plain old JavaScript object. Socreate that graph object here. And I'm goingto return it by the end just like this. Andwhat I want to do is fill up this graph withinformation from the edges. So I'm going toiterate through every edge. So for let edgeof edges, so iterating, through every singleedge, I know a single edge would be a pair.So I'm just gonna de structure out of that,maybe just my two node identifiers, we'llcall them a and b, from the edge. Nice. WhatI want to do is now initialize these nodesas keys of this graph object. So a would besomething like this, I note or this k node,right. So what I'll do is check if A is inmy graph, I think really clean up this code,we better if I check if it's not in the graph.So if the a node is not in the graph, thenwhat I can do is initialize it in the graph.So use it as a key and assign it to be anempty array. And I'll do the same for B overhere. Right, so I'm initializing A and B inthe graph if they don't exist, and once Ido that, then I can safely just add neighborsinto their their edges, right? So I can say,the graph square bracket a dot push B. Sonow I'm saying that right, B should be a neighborof a, but I know that this is an undirectedgraph, right? So that should be symmetric.In other words, then make sure you push ainto the neighbors of B. So it's really importantthat you notice that this is an undirectedgraph. So your adjacency list needs to besymmetric in that way. So if a is in B's neighbors,B should also be an A's neighbors. So that'slooking pretty good. Let's go ahead and seehow that graph looks just with a little littleside test here. So I must steal maybe thissnippet, get that full snippet here, I couldjust run it manually love to make sure I cantest these little helper functions beforeI use them. So we'll give this a run, we shouldjust see the adjacency list form of theseedges here. See how it looks. So that lookspretty good. So I'm seeing that all right,I is connected to J and K. Right? And thatlooks correct based on these edges. Awesome.And I'm also want to make sure that it's symmetric,right. So if i and j are over here that Ishould have JNI over here as well, right,it should be a two way street. Alright, nowlet's work in our real algorithm here, whichwould be some sort of traversal. Now thatyou have a nice adjacency list, you can doeither a breadth first or a depth first traversal.I'm going to implement I think, a depth first.Typically for me, it's just easier to raisepush if I do it recursively. And so I'm goingto pretend I had a function called has path,it's going to take in my graph now. And alsoa start node and an end node. So I want tofind a path from node A to node B, of course,I'm going to assume that this function returnsa Boolean. But of course, I have to writethat function for myself. So stay organizedin our code, we'll say has path. I'm goingto take in the graph as well as node A andnode B. And I think a better name for thesearguments as I'm doing this recursively. Let'scall this one source and this one destination.So over time, we're going to call recursivelyand update this source node. And that shouldbe a familiar pattern to some other problemsresolved. Recently. So think about my basecase. All right, I know that I've has successfullyfound a path when my source is equal to mydestination node, if that's the case in returntrue, because I just found a path. Otherwise,I have to keep looking. So I should be ableto look through the neighbors of my sourcenode. So I could say graph square bracketssource, right? Remember that any point throughthis recursion source represents my currentposition. If I say graph, square bracket source,let's say source was I, I'd be accessing allof ies neighbors, right? So I want to do isreally iterates for let neighbor and, or ratherhave graph of source. So if sources I on thefirst iteration neighbor would be j, seconditeration neighbor might be K. And for eachof my neighbors, I want to travel to them.So call has path, you can keep your graphargument the same needs to change your sourcethough now you're situated at your neighbor,and your destination is fixed, or you're alwaystrying to get to the same exact node. I'mgonna think about what type this returns Iknow this is going to tell me Boolean, right?True or false? Is there some path from myneighbor to the destination, I'm going tocheck. All right, if that call, returns true,I'll be explicit here, then I've just founda path. So just return that true, right, passit all the way back up. And kind of the logicthat we form here is, I know that by definition,source and neighbor are definitely connected.So there's definitely a path between them.They're connected by a direct edge. So ifmy neighbor has a path to the destination,then I know, then the source also has a pathto the destination. Awesome. And so afterthis for loop is done running, let's say wenever find that any of our neighbors makea winning path, then means I finished thisfor loop without ever returning true, whichmeans that I can return false right must bethe case that this source node does not havesome path to destination. So I think we cango ahead and give this code a test run. Ifyou watch the approach video, you'll noticethat there's something important missing fromthis code. But we'll just run it and showyou how to fish here. So here I'm gettingan error edges is not defined what I do horriblywrong, line 34 months ago, line 34 over here.So got to take out this call, don't need thatanymore. That's on me. Let's get that testrun. So that was not the error I was expecting.I am expecting some sort of an infinite loop,though. Perfect, I'm getting maximum callstack size exceeded. So I got like an infiniterecursion really. And that's going to occurbecause we didn't account for the case wherewe have cycles in our graph, right, we needto avoid that. Because if I have a cycle inmy graph, I'm never going to hit any of thesebase cases, I'm just gonna keep travelingaround in a circle. And if that's unclear,make sure you watch the approach video, right.And so like we said, the move here is to addsome sort of data that shows where you'vebeen previously. Typically, the way we dothis for our graph problems is to track somevisited set. So when I make my top level callto this house path, I know that that is theactual function that does that traversal,I'm going to pass along a new argument here.And I'll make it a new JavaScript set. Soif you're unfamiliar with sets, and JavaScript,they're really just a collection of items.And what's really great about a set is ino of one time, I can add something into theset. And I can also check for something withinthe set is going to be very, very quick forour traversal. I don't want to use somethingslow like an array, because to do a lookupor a check within an array, that would actuallybe O of n time, or it's for a set, it's oof one. So I'm going to make a new argumenthere to receive a column visited. What I wantto do is all right check if my source nodeis already in the visited set to do that inJavaScript I can check visited out has. Soif the source node is inside of the visitedset, then I could return false here, right,there's no reason to travel through this nodeanymore. Because if it's an visited then Imust have traveled at previously. And thisis how I can avoid an infinite recursion canalso move this line downward if I wanted to.And let's say that I make it through thisif statement. So that means that all right,this node source has not been visited. ButI'm visiting it right now. So I need to dovisit a dot add source. So this expressionchecks if source is in visited, and this expressionadds source to the visited set. I want tochange a few other details here. Make surethat you pass along the same visited set throughall of your recursive calls over here. Becauseyou want this visited set to be like globalfor the entire traversal right I need to knowexactly where I've been in the past. And oncewe have that in place, that should be everythingwe need to prevent any any cycles from givingus infinite recursion here. Let's give ita test run. Awesome. There's a solution forour undirected path problem. So importantthings to take away here do consider thisproblem, a two parter right? phase one isreally straightforward, just converting anedge list into an adjacency list, which isactually an important skill to practice. Becausewhen it comes to, you know, some problemsyou'll face in the wild, they are all goingto be basically graph problems. But sometimesthey'll give you the graph and like a differentformat, and you can always convert into aformat that you're comfortable with. And fromthere, we have a really core pattern of justdoing a traversal through a graph, but alsoguarding against infinite loops, right. Andto do that, we just use some sort of a visitedset. Hey, programmers, welcome back rightnow want to go over the approach for thisconnected components count problem. So inthis problem we want to do is take an adjacencylist representing an undirected graph. Asalways, with any graph problem, you want tostart by visualizing the actual graph. Andso if you took a picture of this information,it would end up looking like a graph withthis structure. The first thing we shouldnotice about this visual graph is that a hasmultiple connected components. So for example,I can look at this component in pink spanningjust the one and two nodes, I can look atanother component spanning the four or 5678nodes. And finally, a third component justcovering the three node. And that's why wesay that your result for your function hereshould be three, right? Because there arethree different connected components. So let'scome up with an algorithm we can use to countthe components, we know that a general countingalgorithm is going to use some variable, andwe'll initialize that count variable to zero.And the trick here is to use a combinationof both some standard graph traversal code,maybe a depth first as well as some iterativecode. So I'll do along the left hand sideis just list out all of my different nodes.And what I'll do is start by iterating, throughevery node of this list. And what I'm goingto do is when I'm currently at some note ofthis iterative list, I'm going to start atraversal at that node. So right now startingat the node of one, I begin, let's say a depthfirst traversal, you can really implementthis pattern using either a depth first orbreadth first. So let's say I start at theone node over here. What I should do now iscontinue this traversal as far as possible,that's the key to victory here. So from thisone node, I can move to a neighbor of two.And of course, as I travel through these nodes,I want to make sure that I mark things asvisited, so I can avoid loops. And markingthings as visited will also ensure that wedon't double count any components here. OnceI hit that to note, I've actually completedthis full component, there's nowhere elseI can explore. So at this point, I shouldincrement my count by one. So whenever I completea new traversal on some region of the graph,I need to increment my count. At this point,I now fall back to my iterative code on theleft hand side, and I iterate through thenext node. So I now look at node number two.If I take a look at node number two, I seethat I already have it marked as visited.So that means I don't need to start a traversalat that node. So effectively skip the twoand keep the count the same. next iterationI have a three, three is unvisited right now.So I should begin a new traversal startingat this three node, which means I just markit as visited. And since this three is a singletonnode, right, it's not connected to anyone,I would actually complete their traversal,just on the three node. At this point, I'vecompleted a traversal. So I increment my countby one. So now I have a total count of two,I fall back to my iterative code. So I movedfrom the three node to the four node. AndI see that this four node is unvisited, whichagain means I must begin a traversal fromthis four node. And I'm going to expand thistraversal. Starting at four as far as I can,before I go back to my iterative code, right,so I'm going to explore the six, explore thisfive, explore the seven, and finally explorethis eight. At this point, I've completeda traversal. So I can increment my count upto three. And then I have to continue andfall back to my iterative code. So look atthe five node, I see that the five note isalready marked as visited, so I don't starttraversal. And I see that the six node, samething don't need to start traversal sevennote already visited, eight nodes alreadyvisited. At this point, I would be done withthe entire algorithm. And there's my finalcount of three. So a few interesting mechanicshere, right, you're going to need to definitelyimplement some code or some function thatdoes a traversal through some component asfar as possible, then you also need some iterativecode just to potentially begin a traversalat every single starting point. And what youwant to do is be sure to mark nodes as visitedas you traverse them, because only when youmarked a new node as visited and completethat traversal should you increment your count.You're probably wondering the exact detailsof how we implement this in some code, butdon't worry, you'll realize that it's reallyjust a spin off of our previous graph algorithmsin the walkthrough video, but for now, wesee that n is a number of nodes And he hasa number of edges like usual, we know thatthis is really just traversing through theentire graph. So we can say the time complexityis just o v, and the space complexity is Oof n, right, depending on whether you do abreadth first or depth first, you're goingto use that space, then in terms of your stackor cube. And we can also consider using thespace within our set if you use a set to markyour nodes as visited, but overall, it stillwill lead to a linear time and linear spacesolution. Alright, I think I'm ready to codethis one up. I'll see you in the walkthroughvideo. Hey, programmers, Alvin here, right,now let's go over a JavaScript solution forthis connected components count problem. Andso we'll implement exactly the strategy wespoke about in the approach video. So makesure you watch that first, we know that thisis going to require really two different mechanismsare going to need our interactive code justto hop to different connected components.And we also need some traversal code to justexplore some single component as far as possible.And so what I'll do here is let me start withthe iterative code. So I need to begin a traversalat every potential node. So I can say forlet node of my graph really say in my graphhere, because for this problem we're givenlooks like JavaScript objects. So if I sayfor let node in graph that would give me eachof these keys like 015, and so on. And sofor every node of the graph, what I want todo is begin a traversal. So we're going toassume I have a function here, I'll call itexplore. I'm gonna pass in, of course, thegraph, as well as that node. And what I wantthat function to do is do like a, we'll say,a depth first traversal, from that node asfar as possible, right, so probably goingto need to add more logic into this main function.But for now, I think it's about time to actuallyflesh out explore. So I'll choose to do thisexplore method recursively. So we'll defineexplore, it's going to take in a graph, aswell as my current node, I'll just call itcurrent, right. And then from there, I wantto solve this one, using a depth first. Sorecursion is fine. And not much to do here,but really go through my neighbors want toiterate through every neighbor of this node.So I can say like neighbor of graph of current,I recall that graph would be an adjacencylist. So if current is spread this out. Soif current was a node like eight, then onthe first iteration neighbor would be zero,next iteration neighbor would be five. Sohere, I'm just going through all the neighborsof my current node, I just need to not traverseto them. So I can call explore, pass alongthe same graph, that doesn't change. But nowmy new current node would be that neighbor,just like that, and this will perform thebaseline of just the kind of depth first traversal.But we need to also mark things as visited,like we said, in the approach video, that'sa really important a part of the solution.And I want this like visited set to be globalfor my entire traversal. So I'm gonna haveto create it, maybe my main function overhere. So I can create my constant visited,make it a JavaScript set, because JavaScriptsets off for me O of one lookup, and o ofone addition, I can pass this visited setmy reference until all of these calls overhere. So I know I'm gonna receive visitedover here now. Now I want to actually startusing visited. So a few things to note, right,I definitely want to use visited to preventcycles, right? That's one of the main reasonswe always had visited to our graph traversals.So some familiar code here. If I've alreadyvisited this node, so if visited, has thiscurrent node, then nothing much to do here,maybe just return false. Later on, we'll see.The really cool trick we use here by returningfalse, right, actually serves two purposes.return false because this might be a cycle.And then I need to make sure that I pass asvisited set along over here as well. Nice.And let's say that we have a current nodethat is not visited. So this statement isfalse. Well, then, it seems to be that we'revisiting this node right now. So now we shouldadd it into the visited set. Nice. And thenbeyond that, we need to make sure that ourexplorer function is consistent in its type,right? So I'm going to have my explorer functiondo is it's going to return true whenever itexplores like a new node return true. So ifyou take a look at this code, for my functionto hit this line 17 return true, then it mustbe the case that it has already finished exploringall of its neighbors, right, because I knowthat this for loop does the job of exploringall of the neighbors, right? So only afterall of those neighbor calls returned. WillI return true? And that must mean that I'veexplored this component as far as possible.Right? And that seems good to go. And whatI can do is now in my main function, whenI call explore it, now it's going to giveme boolean data, right? If it's exploringa new island, or a new component, it's goingto return true. So I can check. All right,if explorer returns true, then that's a newcomponent. So I can probably increment somecount here, I should have created. So I'llsay 11, counts equals zero, I'm going to incrementthat count, when I find a new component andplus equals one by the end, I should of course,return that counts. And what you'll noticeis, for scenarios where we, let's say iterateinto a node that we already explored, whenI make this call, I know that that call isgoing to return false, because if something'salready explored, it would have been addedto visited. So that's why I'm using some Booleanreturn values for this recursive function.So that code is looking pretty good. I thinkat this point, we might be ready to test thisone, let's give it a shot here. So some prettytricky codes, not very long. And this is areally core pattern here. Looks like I'm gettingan error, we have something wrong here. Solooks like the answer should have been two,but I gave back seven. So I'm counting waytoo high. So what I'll do to debug This oneis really just maybe print out my visited.So this is a very common mistake in JavaScriptwant to bring in, I think this example, Icould test it manually. What I want to besure to do is maybe at every iteration of,let's say this this for loop, I console dotlog with visited associate visited changesevery time. And I'll run this manually byjust hitting run. And let's see what we gethere. So a few things to note, it looks likesome of our keys, or some of our items ofthe set are strings or the zeros a string.And other times they're actually numbers,notice that they're missing quotes, that hasto do with, you know, kind of just JavaScriptobjects, technically, keys of a JavaScriptobject are going to be always converted asstrings, although the data within these arraysover here is going to be number. And setscan actually store both types. And so if youhave like two different types, it's not gonnabe able to figure out like that those reallyrepresent the same node. For example, lookingat this visited set over here, I have likethe number one, as well as the string of one,which is no good. So let's just convert themall to maybe strings. So I'll check visitedif it has the string version of my currentnode. So I'll just do the conversion for me.And likewise, I want to add the string versionof the current node over here. That way, Ihave very consistent types. So let's run thatmanually, again, should just see all of ourstrings now. Awesome. And I think we can runall the test cases. So that's a really importantthing to watch out for in JavaScript. AndJavaScript is pretty unique in that regard.It just automatically converts all of yourkeys into strings. Awesome. All right, programmers,it's all I got for this connected componentscount problem, what you want to do is reallypractice this problem. It's actually a very,very common interview question. And thereare many variations of this problem that we'regoing to do in the future. Hey, programmers,Alvin here, right? Now I want to go over anapproach we can use for this largest componentproblem. So in this problem, we're going totake in a graph, just like we've been doingas of late. And the first thing you shouldprobably do is think of this graph as a picture.So hopefully, you drew it out. So you canreally understand what this is asking. Ourgraph information is already given as an adjacencylist. So it's pretty easy to draw out. Sosince I have a graph like this, the firstthing I should notice is it could containmultiple components, right. So here, I kindof see two separate islands, two separatecomponents. And I want to consider the sizesof each respective component. So if I lookat my first component, spanning the nodes,015, and eight, I know that they have a sizeof four, they're the four represents the numberof nodes within that component. So I'm reallyinterested in a number of nodes have a component,not necessarily the number of edges. If Ilook at the other component that spans thenodes, two, three, and four, that definitelyhas a node group of three. And this problemreally cares about the largest component,so I should just return four, because it'sthe largest component size. So when it comesto what this question is asking, you do havesome familiar patterns if you've been followingthese problems in order and of course, I alwaysrecommend that you do these problems in order.So how can we go about solving this one? Well,I know I'm gonna need some sort of iterativecode that way I can travel and hop to differentcomponents or different islands, I can probablydo some depth first traversal variation thatalso finds the size of a connected component.So let's step through how this algorithm mightrun. On the side. I'm going to list out mynodes to represent how I'm going to do theiterations to be In a traversal at every nodeas my starting point, so I'm going to startat node zero. And since node zero is unvisitedright, now, I'm going to begin a brand newtraversal, starting at node zero. And I'mgoing to mark my nodes as visited as I go,because like usual for our undirected graphs,you want to watch out and prevent any cyclesthat you may get trapped in. And I know thatthis depth first traversal, is going to explorethis full region as far as possible. And bythe power of recursion, it'll be pretty easyto implement some pattern that can count everynode as we traverse through it. So I'm goingto treat each of these nodes as just beinga single note, of course. And eventually,those ones are going to return to my top levelcall, in which case, I can add them all up,getting me a grand total of four. If thisfeels very hand wavy, and you're wondering,like how the heck are we going to code upthat pattern, don't worry, it's actually apattern we've seen before. And so I'll coverthat in detail in the code. Just know fornow, it's actually not a big deal to get thecount of nodes, right. So now that I knowthat the size of this component is four, whatI should do is I guess store it as my currentlargest island or component I've seen so far,because it's the first component that I'veconsidered. At this point, I should fall backto my intuitive code. So I look at the nodeof one, what I should notice is this nodeone is already checked off, it's already visited.So there's no reason to start another traversalfrom this node, because if it's visited, thatmeans I have already explored the componentthat node one is a member of, so I can basicallyskip it, go on to node two in my iteration,since node two is unvisited, I should begina new traversal. Over here, I know that thisdepth first traversal is going to explorethat component as far as possible, it's goingto go ahead and count all of those nodes asone. And eventually some of those counts together,giving me a count of three. And so this nextcomponent has a size of three, I need to comparethat three against my current largest four,obviously, the four is bigger, so the fourgets to stay as the largest. When I fall backto my iterative code, I get to my note ofthree threes already visited, so no reasonto start anew. traversal, four is alreadyvisited, so nothing to do, five is visited.And of course, eight is visited as well. Atthis point, we're done looking at every singlenode within our graph, and we must have exploredevery single component, so we can just returnthe final value that we have stored in thatlargest variable. Awesome. When it comes tothe complexity of this algorithm, it's prettystraightforward. It's basically exactly allof the algorithms we've seen so far, we seethat n is the number of nodes and e is a numberof edges, we know that the time complexityis going to be roughly o of the number ofedges really just exploring through the entiregraph, we can also see that the space complexityis also going to be linear, really just Oof n. Because through all of this, we're probablygoing to be storing all of our nodes in aset right to track visited. And dependingon how you implement your traversal algorithm,whether you use depth first or breadth first,you're also going to use a linear amount ofspace through your stack or your queue. Sooverall, we're looking at a very efficient,linear solution. And so with that, I thinkI'm ready to code this one up. What I wantyou to do though, first is possibly give thisone a shot on your own first cluster, reallyjust utilizing some code that we've seen inthe past. So give it a go on your own. Ifyou get stuck, you can find me in the walkthroughvideo. I'll see you there. Hey, programmers,Alvin here, right now let's go over a JavaScriptsolution for this largest component problem.So this problem is going to be really justa spin off of our last problem. So we'll hopright into it. And as always, make sure youwatch the approach video first. And we'llstart by building our code that will helpus start a traversal on disconnected islandshere, right? This is connected components,we should say. And so I'll start my iteratingthrough every node of the graph, that meansI just iterate through the keys of my inputobject here. Because remember, we're giventhis graph as already an adjacency list. SoI can say for let node in the graph. So I'llgive me the nodes like 015, and so on. Andwhat I'll do is I'm going to start a traversalhere, right? So we're going to pretend I hada function, I'll call it explore size. Andif I give it the graph information, as wellas the node that I want to traverse through,hopefully, it actually does a traversal throughthat entire connected component, right. Andwhat I'm going to assume is, let me assumethat this function actually returns the sizeof that entire component. So that would bea number right, representing the number ofnodes in that component. And so if I havethat should receive it here, call it size.And I know I need some like max value logicfor this entire for loop. So I'm going tocreate longest, initialize it to zero. Andthen from there, I can check. All right, ifthe size of the component I just found, ifit's bigger than the longest, then I can replacethe longest simply longest equals size, thatafter the for loop, I would just read Turnthe longest course I need to write this exploresize function. So I'll implement this as atype of depth first. So I'm going to makeit recursive, as for size, taking the graph,as well as our current node. And a few thingsI should watch out for here, they tell usthat we have an undirected graph. And so weneed to make sure that we avoid any cycles.So we're also set up here is some classicstructure, I'm going to use a visited set,we're going to use a set because it givesme O of one lookup and o of one insertion.So now that I have my visited set, I can passit along, as I start the traversals. And nowlet's work on a base case, as well do to getgoing is check if I visited this node already.So if the visited set already has this currentnode that I need to return, basically avoida recursive call. But I also want a consistenttype here, right, so I'm assuming that thisfunction gives back a number representingthe size at some point in my traversal. IfI get to a node that has already been visited,that means I counted it already. And so I'lltreat it as zero right now, because I don'twant to double count my nodes, right otherwisewould be inaccurate here. And now beyond that,what I can do is maybe create a variable here,I'll call it size, I'm going to set that equalto one to represent the current node I'm onright now, right? If this condition is nottrue, then it's the first time I'm seeingthis node, so I need to count it. And we'llalso be sure to do is add it to visited thatway I don't get into a cycle into the nodelater on. Nice. And at this point, I needto make my recursive call on the neighborsof this node. So like we usually do couldsay for let neighbor of graph of node. Soremember your shape of data here. So if nodewas a key, like five, when I say, Neighborof graph node, that would iterate throughthe neighbors a five, zero, and then eight,and so on. And so here, I make my recursivecalls, I'm gonna call the same function exploresighs, pass along the same graph. But nowyou're situated at your neighbor, and youcan provide the same visited set. And here'swhere I do my recursive leap of faith, right,I'm going to assume that this explore sizefunction is working. So if it was working,what would it give back, it would give meback a number representing the size of thatgraph, right beginning at my neighbor. Sowhatever number I get back here, I just wantto increment my size by that, right. And thatwould accumulate a basically a count of allof the nodes in this fully connected component.And after I'm done exploring my neighbors,I would have explored the entire componentfully. So I can just return my final answer,which would just be the size over here, reallyimportant thing you need to do is make sureif you follow this kind of strategy, you startyour size equal to one, and you add to itover time, because this one represents thecurrent node that I'm at, I know that everycall is going to count its own node. So overtime, this will actually accumulate everythingI need. So feels pretty good, have our nicevisited logic. And we already wrote our mainfunction here. Notice how we're splittingup this code in a nice little helper functionhere, I think it's the best way to expressthis, it's very similar to some previous problemsthat we've done. Right, I think at this point,let's go ahead and give this a shot. See,what we get, should be able to put it througha few different test cases. Nice. And there,we have the largest component to problem.So a few things, I want to draw your eye toremember that for your graph problems, oryou have disconnected components, you're goingto need not only your traversal code, butsome just iterative mechanism, usually justa loop to make sure you can hop to differentcomponents, right? Because if you only hadyour regular like traversal function, by definition,there is no edge between separate components.So you would never be able to explore thefull graph. Otherwise, alright, programmerspractices, and I'll catch you in the nextone. Hey, programmers, Alvin here, right.Now let's go over an approach we can use forthe shortest path problem. So here we haveanother graph problem, and your graph is goingto be given as an edge list. So the firstthing we should probably do is, of course,visualize this graph. And in the context ofyour code, it probably would be best if youconvert it into an adjacency list. Since we'veseen that pattern a few times in some recentproblems. I'll leave that part to you. Butwe're going to end up with a graph that lookslike this. And in this problem, we're alsogoing to be given a two nodes here, let'ssay W and z, what I want to do is return thesmallest path between these two nodes. Andhere I have two obvious paths, right? Oneway I can get from W to z would be to go throughx and y. And there I can see that that pathlength would be three. Do note here that we'regoing to consider the path link as the numberof edges within the path. So not the numberof nodes, right? So that means how do I calculatethree here? What's really just three lines,right, three edges. That's one way to getfrom WC another obvious way to get from Wto z would be to go through VI, which case,I would only need to use two edges. So thatpath line is of course two. And this problem,what I want to do is return the smallest possiblepath length. So I should return the finalanswer of two here. So we know that this problemis going to require us to do a graph pathfindingalgorithm. The question is, which one shouldwe take, we either can choose, of course,a depth first traversal, or a breadth firsttraversal, I'll cut to the chase here. Andboth of them would actually give you a strategythat works, meaning you can solve this witheither a depth first or a breadth first strategy.But maybe one of these algorithms would bebetter than the other. So let's consider thepossibilities. So let's say I had some largegraph, well think abstractly right now. Sokind of just looking at an abstract example.And let's say I was stepping through somedepth first traversal. Let me say I have mystarting node in yellow, and I'll have mytarget node in blue. So what I want to dois, again, figure out what's the minimum pathdistance between these two nodes, obviously,you know, just in the long run, you shouldget an answer like two here, right, becausetwo is definitely the shortest path betweenthese two nodes. If we did a depth first traversal,I know that depth first would force me tolook in one direction as far as possible,until I have to switch directions, right.So for my starting on yellow, let's say wemove to the right, that'd be one edge andmove to the right again, two edges move tothe right, again, three edges. At this point,I can't move right anymore. So let's say youmove downward, so at 456 have to switch directions,again, seven, eight. And at this point, wekind of already see that this is going toend up possibly getting to the blue targetnode. But that wouldn't be the shortest path.Something unfortunate here is although mystar and nodes are really close together,a depth first traversal could be unlucky inthat it may search in a totally wrong direction,and snake all the way through the graph untilit eventually finds my target node, at whichpoint I definitely don't have the shortestpath. So I think a breadth first traversalis going to be more useful here. So let'ssay start at my green node, still my samestarting point. And if I did a breadth firsttraversal, I know that breadth first meansI'm going to explore all the directions veryevenly. So it would look like this. So I wouldexplore all nodes one edge away from my startingpoint. And then from there, I would beginto explore all nodes two edges away from mystarting point. And at some point, I'm goingto hit my target node. And if it's the firsttime I'm seeing my target node, then by definition,I must have just found the shortest path,right, the shortest path would just be two.So that's my high level argument for why abreadth first search is going to be more useful,in my opinion, for this problem, let's stepthrough this process a little more algorithmically.So let's say I had my original graph. Andif I'm gonna do a breadth first traversal,I know that I have to use a queue right nomatter what a queue is what gives you thatbreadth first order. And what I'll do is eyesthe items of my queue, I'm going to storenot only the nodes, but also the distancefrom my starting point, that means I'm goingto initialize my starting note on the queuealong with the distance of zero. And thatrepresents the fact that all right, that noteof W is zero edges away from the startingpoint, because it itself is the starting point.So at any point in time, the items of my queueare always going to be pairs, right of nodecomma distance. So now we're going to beginour general algorithm, I'm going to keep iterating.While my queue is not empty, a single iterationof breathless would remove the front end ofmy queue, and I'll label it as my currentnode. At this point, I should check Alright,is my current node of W, the thing I'm lookingfor? It's not, so I need to explore W's neighbors.So I can look at the x node. And I know Ineed to add it into my queue. But when I addit into my queue, I want to make sure I tagit with a distance. So if my current nodehas this zero, I know that a neighbor of thisnode would have distance one, so I just incrementthe current distance by one. So onto my queue,I put an item that says x comma one. And Ihave a similar scenario for this V node. It'salso a neighbor of W. And so I put v commaone on my queue as well. At this point, Ican go to my next iteration, or move the frontof my queue. So I look at the x. And thenI look at X's neighbors do bear in mind thatbecause I have an undirected graph here, xreally has two neighbors, right, it has was a neighbor, as well as y. So somethingyou should already know is I need to trackvisited. In other words, when x is going toconsider its neighbors, it should really onlycare about the Y, right, I don't want X toput w back on the queue, because then I wouldget an infinite cycle. So I'm just gonna lookat the Y over here. I'm going to add it tomy queue. Because I know my current note ofX has a distance of one y must have a distanceof two always just incrementing the distanceby one. Cool. And then I carry on with thisalgorithm. I removed the front of my queuenow, which would be the V note. And at thispoint, I can consider V's neighbors, and Ido See that one of its neighbors is actuallythe Xena, that's the only unvisited neighbor,I'm going to be sure to add z into my queueand tag it with a distance of two, right,because if my v has distance one, its neighborwould have a distance of one grader. At thispoint, you can already see how this algorithmis going to work out. Eventually, this z nodesgoing to leave the queue, and that would actuallybe my target node. So since I've added a nodeinto the queue that matches my target, I knowI have my final answer. The two here doesrepresent the number of edges we took in thatlogical path. And I would, of course, justreturn that too. So for the most part, thisalgorithm just sounds like a classic breadthfirst traversal. Using a queue on a graph,the only interesting bit is now we're alsogoing to track the current distance. You know,when it comes to counting the length of apath, you need some counting mechanism. Andso if you begin your queue with your startingnode with a distance of zero, every time somethingleaves a cube, and adds its neighbors, itshould increment that distance by one. Andlike you already guessed, this algorithm ispretty efficient, because we don't have totraverse through the graph more than one.So we'll see that this has a linear complexity.Alright, I think I have everything I needto code up this one, I'm sure you're wonderingabout these implementation details. So whatyou want to do is possibly give this implementationa shot on your own. And if you need some help,you can find me in those walkthrough videos.See you there. Hey, programmers, Alan here,right. Now let's go over a JavaScript solutionfor the shortest path problem. So we'll jumpright in, hopefully, you watch the approachvideo. And so we'll start by converting ouredge list input into something more usefulfor our traversal like an adjacency list,we're going to write a very classic function.When I call it build graph, like you expectit takes in the edges. And I want it to returnan adjacency list. For me, that means a JavaScriptobject, I'll call it graph, by the end ofthis function, this will help I'm going toreturn the graph and some common code, I'mgoing to iterate through every pair, right,basically every edge, I'll say, for left edgeof edges. As I'm iterating, through everyedge, when I want to do is unpack that edgeinto its component nodes, I'll call it a andb. And now I can start formatting my adjacencylist. So I know I want the keys of this graphto be obviously the nodes, I want the valuesto be an array of the neighbors of that node.So what I'll do is, it's the first time encounteringa node, I'll check. Alright, if this a nodeif it's not in the graph yet as a key, thenI should create it for the first time. Souse it as a key and initialize its value toan empty array, basically, at the start isgoing to have no neighbors. Likewise for B.And then, at this point, I know that A andB now definitely exist as keys within thegraph. And so I just want to add those neighbors.So if I have an edge, like w comma x, I knowx is a neighbor of w, and w is a neighborof x. So simply put in say, graph a dot pushB, and then just the inverse of that shouldbe good to go. Cool. So that should give usour graph. Let's go ahead and use that inour main function now. So we'll just say graphequals build graph on the edges. And whatwe want to do now is actually work in ourbreadth first logic, like we said from theapproach video. So a few things I'm goingto do, I'm going to definitely set up my queue,we said that the key to victory here was tonot only store the node in your queue, butfor every like frame inside of your queuealso store its distance from node A. So I'lljust use like a pair of things. So the elementsof my queue are going to be always a pair.And I'll throw on the initial node A, andalso the number zero, because at the start,right, this node A is zero edges away fromitself. So that's good to go. And over time,I'm going to be incrementing. This number,it seems nice. And so let's keep on keepinon here. All right, a while loop, classiccondition would be all right, while your queueis not empty, then I shall remove somethingfrom the queue. So always remove from thefront if you want to follow a true breadthfirst order. So I can do do dot shift. Andthat will give me back an array or give meback one of these sub arrays here. I knowit's always going to be a pair so I can justunpack. And I'll just say alright, grab thecurrent node as well as the distance. Nice.I'm going to check the node here that I justremoved from the queue. If that node is nodeB, that I must have just found a path andI know the distance in that path, I can justreturn it. But if this condition is not true,then I need to keep searching through my graph.Since that means I need to add this nodesneighbors to the back of the queue. So I'mgoing to iterate remember that we have adjacencylists the entire time. So I'm going to say,for, let's say, Neighbor of graph of node.So get all the neighbors of this node. Andwhat I'll do is just add those neighbors intomy queue. So q dot push, neighbor, try toremember what the form of our graph is overhere. Maybe as a quick little spot check,make sure on the same page, let me just consoledot log, the adjacency lists, let's say wetook this example manually, just paste itdown below. And I'll just give it nice littlemanual runs, I'm not running the test casesquite yet. So we converted this edge listinto this adjacency list, right. And whenwe say no to something like W, when we saygraph, square bracket, no, that would giveus this array, co authored sorters, iterating,through all the neighbors of this node andadding them to the queue, one thing we shouldwatch out for is when we push things backonto the queue, we want to maintain the sameformat. So I actually still want to maintainpairs. So I'll make the first element of thepair, the neighboring node on the second elementneeds to be the distance. And since it's aneighbor, its distance would be plus one overhere. So that's how I'm growing and countingthe distance. So let's give this a test run.There are a few things we need to work onstill, though. But we'll pass a few of theseexamples, at least until we timeout on a particularexample. One thing this code is missing isany cycle prevention, right? I know that it'sgoing to be a very common scenario, becauseI have an undirected graph, right. And sowhat I'll be sure to do is maintain a visitedset, sort of pattern that you're used to,we're just gonna implemented for our iterative,breathless right now. So start out with aset. And when you do this iteratively, themove would be to make sure that if somethingis added to the queue, it should also be markedas visited. So if I initialize my queue withnode A, then I also want to initialize myvisited set with node A, just like so. Soif you're unfamiliar with the set constructorin JavaScript, if you want to initialize itwith some values, you actually have to passin an array containing those values. So thevalues of my visited set are just going tobe the nodes write the node IDs. Cool. Andthen I want to work that logic into my whileloop. And so whenever I'm about to add somethinginto the queue, that is, I'm going to adda neighbor into the queue, first check ifthat neighbor is not visited yet, so onlyif not visited has neighbor. Right, so onlyif this neighbor has not yet been visited,then I should add it to my queue. And if I'mabout to add it to the queue, like we justsaid anything that interest, the queue shouldimmediately be marked as visited. So hereI'll say visited, add, the neighbor net shouldavoid adding any particular node more thanonce into the queue, avoiding any cycles.Awesome. So that feels pretty good. Let'sgive that a test run. Now. We hope to nottimeout at least, all that same example, we'reactually returning undefined where we expectnegative one. So if you look at the actualprompt, they tell us that, alright, if youcan't find a path between A and B, then youshould return negative one. Let's look atan example or test 04. And you kind of drewit out, you would see that there would beno such path that connects B to G. The reasonwe're returning undefined right now is we'regonna finish our traversal mean, meaning ourqueue is going to empty out. And then we'rejust going to hit the end of this function.And if I don't hit a return line by defaultin JavaScript, I'm going to get undefined.So we know if we finish the while loop, andwe never found node B, then we can just returnnegative one, that must mean that there isno such path that connects a to b. So let'sgive this a test run. Now. This should beour final version of our shortest path algorithm.Awesome. So be sure to practice this algorithmbefore you move on. And do make sure thatyou understand the choice of breadth firsthere over depth first, for most of your basicjust graph problems that require you to calculatea shortest path path meaning just the numberof edges. Typically, you'll find breadth firsteasiest way to calculate that hey programmers,Alvin here, right now let's go over to theapproach for this island count problem. Soin this problem, we're going to be given a2d array representing a grid of land and watershere we have l characters representing land,and W characters representing water. Let'stry to visualize this. In this problem wewant to do is return a number representingthe number of islands on the grid. We're goingto consider an island as a vertical or horizontalconnected region of land. So in this particularexample, we should return four. Because thereare four different islands, we can label themas such, this is going to be any type of problemsfor us. And we should really think about itas if we have a graph, I'm going to referto these style problems as a grid graph. Andso although we're not given any explicit likenodes and edges, I can still think about positionsof this graph as nodes. So for example, let'sconsider the indices here. So I have my rowindices along the left hand side, and my columnindices along the top. And I can designateany position of this grid using a pair ofrow and column. So for example, if I lookedat position three comma four, that would bethis position over here. And what I shoulddo is mentally think about a position as ifit's a node. And if I met some node, I dohave some potential neighbors. given any positionof the spread, I have at most four neighborsin the up down left and right directions.given any position of the grid, it's reallyeasy to determine what our potential neighborsare, it's really just a matter of adding orsubtracting one from either the row or thecolumn. Let's generalize this formula. Solet's say I was at some position, we'll callit our see, if I want it to go upward, thatwould mean you decrement, the row by one,keep the column the same. If you went down,that would mean increasing the row by one,if you went to the right, that would be increasingthe column by one. And if you want to go left,then you should just decrease the column byone, do bear in mind that the top left positionof our grid is going to be 00. And that'swhy we have this type of arithmetic rule.So now that we're starting to frame this gridproblem, as if it's a graph, we can use somecommon patterns, I know that this problemis really asked me to count the number ofconnected components or the number of islandson this grid. So I'm going to need some iterativecode, probably some nested loops to just iteratethrough every potential Island and start sometraversal at that island. So when it comesto our iterative code, we just want nestedloops to iterate through every row column.That means the iterations should look somethinglike this, just moving left to right. untilwe finish around which case we can go to thenext row. Let's actually iron out the mainlogic that we need in our algorithm. So let'ssay we start or nested loops from the verybeginning, what I do is check my current position,what I want to do is check if my current positionis land right now it's water, so I can justcontinue. On the next iteration, I do havesome land position. And since I'm on a pieceof land, right now, what I want to do is explorethis land region as far as possible, probablyusing some depth first traversal. And do bearin mind, like most of our undirected graphproblems, we're going to need to be sure tomark things as visited, so we don't get trappedin any infinite cycles. So for example, ifI started a traversal, at this position, Ican go downward. But I can also go upwardfrom here. And I can bounce back between thetwo going up and down, giving me an infinitecycle. So we know how to fix this using allof our graph mechanics, right, just use avisited set. So if I do a depth first traversal,starting at this position, I know I'm goingto mark off all of these land pieces as visited.And what I also want to do is make sure thatI increments accounts, representing the factthat I've just explored some new island fully.So right now, my count zero, since I justfinished exploring something now my countis one. And at this point, I can fall backto my iterative code to scan for another island.So I move to the right, it's water. So continue,water continue. Now I have another island.And again, I just do some depth first traversalthrough it. And of course I increment my count.This pattern will follow right? Eventually,when I hit the new row, I could be at a landposition. But I should also make sure thatthis land position is unexplored, right. Sosince I'm at position one, comma zero, andthis land has already been explored, I don'tneed to begin a depth first traversal. AndI also don't need to begin a traversal here.And this continues, avoiding starting a traversal.Wherever I have a visited piece of land, weknow eventually, we're going to hit a newisland like this one, where I have a pieceof land that is unvisited. So at that point,that's my criteria for starting a new depthfirst traversal, I explore this region, incrementmy count, and continue business as usual untilI hit this final island that is unvisited.And so I visit it and increment my count.And by the end of my iterations, I shouldhave my final count of four. So that logicis actually pretty straightforward, just avariation of our classic connected component,counting logic, except now we're adjustingthe criteria we use for looking at neighbors,right, our neighbors are actually going tojust be either above downward to the leftor to the right of our current position. Wetalked about the complexity of this algorithm,we should consider the size of the input andthe fact that it has two dimensions, right?So if I say that R is a number of rows, andC is a number of columns, well and the iterativecodes pretty straightforward, I know that'sgoing to give me r times C iterations. Andif I also consider any potential in depthfirst traversal I do starting at some land.In the worst case, I could have one GiantIsland, which is also going to be our timeto see. So the overall complexity, it's justgoing to be our time See, the space complexityfor very similar reason is our time see, becauseimagine that we mark all of these positionsas visited, that probably means we'd haveto add them to some set. Right, so we haveour time see different positions. And by theend, I could add each and every one of theminto my set, the space complexity of our time.See also includes any traversal related datastructures like stacks, or queues, dependingon how you implement this one. So overall,this is going to be a very efficient solutionto solve this one, what you should do is probablygive it a shot on your own first, if you getstuck, you can find me in the walkthroughvideos. I'll see you there. Hey, programmers,Alvin here, right now, let's go over a JavaScriptwalkthrough for this island count problem.So as always, make sure you watch the approachvideo first. And we'll jump right in. So weknow that this is really just a spin off ofour kind of graph connected components problems,except now we have a grid graph, right? Ican still think about like this grid as ifit's a graph, because if I think about anyparticular position of this grid, I know Ihave some neighboring positions that I cantravel through mainly, my four neighbors Up,down, left and right for me, let me startmy laying down some iterative code that canbegin a traversal at every node or every positionof this grid. That way, I can start consideringdifferent islands, right. So I'm going touse just a for loop for this, I'm going toiterate through every possible row columncombinations every position. So I'll say Requals zero, iterate up to the length of thegrid, so grid dot length to our plus equalsone, and do something very similar for mycolumns nested inside, right? Watch out forsome details here though, looking at the examples,we can't actually assume that we're alwaysget a square shaped grid square meaning likeas if the number of rows was the same as thenumber of columns, because sometimes I'llhave like an asymmetric grid occasionally,right? If I look at this very first one, itlooks like the width is going to be five here,but the height is six. So separately for thecolumns, I want to reference the column linesover here. So we're gonna say grid, zero length.Nice. And so at this point, I have some rowcomposition, I want to begin a traversal,let's say a depth first traversal at thatposition. So here's where I invoke some likehelper function, that will make it a littlebit, I'll call it explore. And what's goingto do is, of course, taking the grid information,as well as the row column I want to traversethrough nice. And at this point, I think we'llactually hop to building this this helperfunction, then we probably need to fill outsome more logic within our main driver functionhere. So let's bake this explore helper function.So taking the grid and your row column, andsomething I should also consider is becauseI know that this is really a type of graphproblem, right? I want to prevent infinitecycles, right? So consider this, let's sayI was somewhere in the middle of my traversal,let's say I was at this piece of land, I knowthat this piece of land is going to travelthrough its right neighbor. And it could bethe case that this piece of land now travelsits left neighbor, so I go left and then rightand then left and right. Now it gives me aninfinite loop, right. So whenever you havethis notion of like undirected graph or undirectedconnections, then always guard with a visitedset. We've seen this pattern before. So maybeup top globally, for the entire traversal,I'll create a visited set. So in JavaScript,just a new set, you're probably wondering,you know, what am I going to make the membersof this set? Well, I need to designate positions,right? Think about it as if positions arelike the nodes in this grid in this graph,right. And so what I'll do is pass along thisvisit set, so I can accept it as an org overhere. And when it comes to using your visitedset, what you want to do is make sure youcombine your row and column because togetherthey designate your actual position. I thinkthis is actually worth going through specificallymore of like a language thing in JavaScript,compared to other programming languages. Soquick aside over here, let me get myself somemore room might be a while. Because if you'reunfamiliar with sets, and you don't kind ofknow, their nuances, might actually hit youin the butt later on. So let's say I had aset so I'll create an offset. So can you setand let's say I added I don't know, like anarray containing a row column position. SoI'm gonna say is, alright, maybe I had position,I don't know, one comma three. And I addedthat into my set. So I do s dot add that position.This is actually a common gotcha in JavaScript.If you put any like reference types, likean array or like an object into your set,it's actually going to check for referenceequality when you check for existence lateron. In other words, now I can't really doconsole dot log s dot has one three, becausethis array literal is technically a differentarray in memory. So I wish I could get liketrue back in this scenario, but I'm not goingto get a true. So we'll just run that manuallysee what we get. So like, we say, we're gonnaget a false here, which is not so good. Soinstead, your Fix would be to actually convertthis into some string data. So instead, maybewrite as if you had one comma three, becausestrings are primitive types, and I would actuallybe able to store that string. So wheneverI say the string literal, this would actuallygive me a match now, so I should get a nicetrue here. Awesome. So we'll want to use thatpattern to our advantage. And so maybe I'llstart by creating some position variable,that's going to be like the string of FIDEa version of our position. So just take myrow, maybe add a comma, and also put the columnhere. Nice. And the reason I want to commaseparate is, I need to have different boundsfor my row and column. In other words, imagineI had a row of let's say, 12. And I had acolumn of four. If I turn that into a key,or a position, that would give me positionas looks like 12, comma for another scenario,let's say I had row one, and then column 24,that would give me a position of this right?one comma 24. Right, it's really importantthat you put a comma to separate your rowand column positions, because imagine, I didn'tput the comma, then it would have a collisionhere, I have two totally distinct positions,right? 12, four, and 124. And if I don't puta comma, they look like they have the sameposition key. So that's why I need to commaseparate them. Common gotcha there. But nowthat I have this position, I can use it tomy advantage in this visited set. So if I'vealready visited this position, so if my visitedhas this position, then I should exit, right,I need to return something. And I want thisexplorer function do something similar, likewe've done in our old component problems,I want it to return a Boolean indicating whetheror not this is a new island that I'm exploring.So if it's visited already, that's definitelynot new, right. So just return false, meaningit's not a new island. If I make it past thisif statement, in other words, if positionis not in visited, that I need to mark itas visited right now, second, do visited,add this position. So now I have my core likecycle prevention logic. Beyond that, I havea few other scenarios, we know that in ourtraversal, we're going to look at our differentlike neighbors. And so what I want to do ismake sure that I'm in bounds here. So I'mgoing to check, like to split this up intovariables, I'll say, one, a boolean variablecalled row in bounds. And I'll do is justcheck if zero is less than or equal to therow. And that row is strictly less than willsay, the length of my grid. So I'm just checkingto see if my opposition is in bounds here,I do a quick check, I need to be inclusivewith zero because zero is a totally validindex, right? I need to be exclusive withthe length because imagine I had a grid withlength five, it's last valid index is four.So I need to be strictly less than here. AndI'll write a similar variable for my columnin bounds, just like this. And at this point,I can write a nice semantic if statement check,all right, if your row is not in bounds, oryour column is not in bounds, then exit, right?So return like before I can return false,right? Because I should not consider likean invalid position and a balanced positionas an island, right? So that's looking good.Final base case I need though is, what ifmy current position is water, right? I onlywant to do my traversal through land. Andso I'll add another statement for that. Soup here, I can check. All right, if my gridat row column, if it's equal to water, thenalso return false. No reason to count it,it's really important that you put this inbounds check before you index into your grid,right? Because imagine that your row and columnwere out of bounds. If you write line 15 likethis, immediately, you're going to get anout of bounds error. So start with your guardto check if you're in bounds if you want itto because most of these conditionals theyall return false have the same consequence.You can probably or them together. TypicallyI like to keep them separate. That way I alwaysremember to write them typically for likeyour grid graph problems. This is very canonicalcode. Alright, so if I make it past all ofthese base cases, and I have the recursivecase, so I must be at an unvisited piece ofland. And when I want to do is do my depthfirst traversal, right. So here's where Iexplore my neighbors and I have four neighbors.If I wanted to go above that I decrement,my row by one, keep the column the same, passalong the same visited, because remember,we have like the array indices here. So thisis row zero, this is row one. So we'll lowerrow numbers mean upward, in the same way,lower column numbers mean to the left. Sothis is up, this is down by do just minusone over here, that would be to the left,then plus one on the column would be to theright. Cool, and I can keep this code veryflat as it is something that I'm a huge proponentof when you write recursion, for the mostpart, I always try to make sure that I don'tlook before I leap. In other words, just fromthis logic alone, it couldn't be the casethat row minus one is out of bounds. But that'sokay. Because if it's out of bounds, whenI evaluate this call, it's going to immediatelybe caught by this base case, right. And ifI express my logic like this, if I don't look,before I leave, if I just leap and then catchmyself with the base case, you don't haveto write repetitive code. In other words,some people write code like this, where it'slike, Alright, if row minus one inbounds kindof using pseudocode. Here, they would haveto write row plus one inbounds. And you wouldhave to write a guarding if statement aroundevery recursive call, instead, just writeone base case. And you can catch all of thesedifferent out of bounds, right. So that'swhy I prefer it this way. And so I know thatby the time I return out of these recursivecalls, I'm back at this segment of my code.And what I can do is return true because Imust be finished with that traversal. Andthe reason I'm returning true is true symbolizesthat I've just finished exploring a brandnew island, so I need to count it. Nice. It'salso consistent with the data type, I haveBoolean for this explore function. So forthe most part, this looks like really justa spin off of our previous like graph, depthfirst code. And now I want to use that booleandata in my main function here. So here's whereI can actually count my islands. So guessI really need some logic here that says initializesome counts equal to zero. And whenever youfind a new island, increment that count. Soif I just have found a new island, we're goingto get back true from this this call, right?Because remember that I'm beginning a traversal,starting at this row column position. So ifit gives me back true, then I can totallyincrement my count by one. Notice that wheneverI begin a traversal on a position I've seenbefore, it would have been added to visitedbefore. So I would return via this if statementon line 21, I return false. If I return false,then I don't double count that island. SoI do need a combination of both iterativecode to potentially leap to different islands.But I can use a visited set to prevent myselffrom double counting any particular Island.So this is looking pretty good. Let's notforget to of course, return our counts atthe end. Let's give this a run. This willprobably be the first in a series of theselike grid graph problems. Really try to understandhow we can think about still a grid as ifit's a graph, right? We just have differentrules for how we look at our neighbors. Right?Now, a node is really a position and its neighborsare its four neighbors Up, down, left andright. Alright programmers, I want you topractice this pattern because we're goingto see it in the next few problems. I'll leaveit to you see in the next one. Hey, programmersoutlane here, right now let's go over an approachfor this minimum Island problem. So we'regoing to be given here a grid containing awater inland really just some characters insideof our grid. So of course, as always, let'svisualize this. And what I want to do in thisproblem is return a number representing theminimum Island size, we're going to consideran island, a connected region of verticalor horizontally connected pieces of land.So for this particular input, our answer shouldbe to looking at our grid, I have three separateislands. And they all have different sizes,right? sizes, a four, two and five, I justchoose the smallest of the islands. So thatwould be the two over here. So how can I actuallycome up with a strategy for this one, youshould already know that this is just a spinoff of our previous a grid graph problem,where instead of doing just a count of thenumber of islands, now I want to find thesizes of islands. I know to actually lookat different islands, I'm gonna need somenested code, but I'm also gonna need somedepth first traversal code to explore a singleIsland. So overall, this should be a prettyclassic strategy for us. So let's say we startattacking this we know we're going to beginour nested loops in the top left corner Andif our current position is water, then weactually don't need to do anything. next iteration,I have some land. At this point, I could beginon my depth first traversal. And I know thatI should be marking things as visited to avoidany infinite loops, right. So by the timethis traversal completes, I'm going to markall of these guys as visited. But I also wantedto determine the size of this entire islandregion. So every time I get a position thatis land, I should treat it as one. And thenwhen it comes to how I implement on my traversal,I can just gather up these ones, right, justadd them all up. So that would look somethinglike this. And for my top level call for thattraversal, I should get an island size offour. And so if that kind of traversal algorithm,especially how we compute the size of theisland, is pretty hand wavy, don't worry thatwhen we actually go through the code walkthrough,it's just a matter of some recursion, andsome recursion we've actually seen beforein past problems of the course. But any case,now that I have this island size of four,it's actually the first island that I've seen.And so I'm going to consider it the mid sizeso far. But I need to keep looking in casesomething is smaller. So move to the right.So if it's water, I do nothing, water again,do nothing. Now I have another islands, Ibegin my traversal market these as visited.And when I find the size of this island, ofcourse, it's going to give me two, I comparethat to to my current mid size two is smaller,so I store two as the mid size so far. Andwe just continue business as usual. Note thatwhen we get to a piece of land, we reallywant to make sure that it's land, but alsoa piece of unvisited land. So right now onthat piece of land, but it's visited, so Ishould not wear I don't need to start traversalhere. Likewise, for this position. Eventually,I'm going to hit some new unvisited land,in which case I should begin my traversalat Explorer, this region, and I want to countup all of these pieces of land. And I shouldrealize that the final size of this islandwould be five, I can compare that five againstmy current min, five is bigger, so the sizeof two gets to stay. And I can just end upreturning the minimum size by the end of thisalgorithm, basically representing this islandof size two, the complexity of this algorithmis straightforward, we should say that thesize of our input is r times C, because wehave our rows and C columns, in which casea time complexity is simply our time C, right,we have to iterate through every row columnwithin the grid. And even when we begin atraversal, in the worst case, we could havean island that spans the entire grid, in whichcase it would also be our C. Right. So overall,our full complexities are time c space complexitiesare time C as well. And do know that thisis technically a linear solution in the sizeof the grid, right because the grid itselfis exactly r times C positions. So with that,I think we're ready to code this one up andtry it on your own first. And if you get stuck,I'll catch you in the walkthrough videos.See you there. Hey, programmers, Alvin here,right now let's go over a JavaScript walkthroughfor this minimum Island problem. So we'lljump right in, make sure you watch the approachvideo. As always, this is just a nice spinoff of our classic island hopping logic. Butfor a grid graph, right. And so let's startwith the iterative code that can help us begina traversal. Starting at every different positionof our grids, that just means some nestedloops. So start by iterating through all ofthe rows and columns. So r equals zero, goup to while r is less than length of the grid,also do our plus equals one and very similarloop for my column. But do make sure thatyou reference your inner column line becauseyou could have like a rectangular shaped gridover here. And what I want to do now is begina traversal starting at every row column.So I'm going to assume I have a helper functionhere that does that traversal, I'm going tocall it explore size. That's because in thelong run, I'm interested in the size of thatisland, right, so like a number representinghow big or how many positions that islandspans. So I'm going to pass along the gridinformation as well as the position. And Iknow when it comes to all of these like undirectedgraph, traversals should probably guard againstyour loops. And I have some foresight here.So I'm going to pass along a nice visitedset, which I can maintain globally for theentire traversal because there's only a goodreason to explore a position once right. SoI'll create const visited gonna make it myneighs JavaScript set. And a few reasons forthat. Well, for one JavaScript set, givesme O of one lookup, but also o of one insertion.So it's going to be a really quick data structureto use. And from there, we probably have toadd some more logic over here to actuallydo something with the size but for now, Ithink I'm going to switch gears and actuallytake a look at building this helper function,right. So I think the best way to build thistraversal is to use is a deaf purse, typicallyjust my go to for problem like this, it'sgoing to take in I know the grid, the rowin the column and also visited, I need somea base case is very classic base cases, I'mgoing to start by checking if this row columnposition is inbounds. So my favorite patternfor that is to split up in some variablesjust makes it easier to read and debug. SoI'm going to say is my row inbounds and justmake that like a boolean variable. So I'llcheck if, let's say, zero is less than orequal to the row, I need to say and right,and that row should be strictly less thanthe grid length. So this Boolean would onlybe true if it's in bounds, right? And somethingvery similar for my column bounds should bebetween zero and grid zero length. Nice justlike this, I believe. And then I can writea nice if statement using both clauses. SoI can say, all right, if let's say your rowis not in balance, or your column is not inbalance, then you're definitely at a bound.So you should probably use some base casehere, right? So we're all choose to returnhere is zero, because I want to keep a consistentnumber, right consistent return type. Thatis, I know that this function has a kind ofgoal of returning the size of the exploredislands sizes a number. So even in my basecase, I need to make sure I return some typeof number, returning zero to represent that,hey, if this is out of bounds, it's not goingto contribute anything into the count of thesize, right, which is good to go. I need someother base case here. What if my positionis inbounds. But what if it's actually water,I don't want to count that as well. I onlywant to count islands. So land right. So quickfix, what I'll do is add a new base case,I can check if my grid at row column, if it'sequal to the water character. So a capitalW can also return zero. If you want it to,you can also maybe merge these into like asingle if statement, just write a bunch ofORS, I kind of like them separate becauseit's just easy for me to remember what eachof them does write a final conditional havehere is alright, if I make it past both ofthese base cases, it might be the case thatthis position is land, but it's land I'vealready visited. So here's why I work in myvisited logic, I'm going to represent a position,like we said in the last episode as reallyjust a string. So I can put it as the membersof my visited set. So I'm going to say positionto have to be the row plus a comma plus thecolumn. So just representing the position,that's because I can't add like an array intoa visited set, and then look it up later.And so if visited has the position, then it'sa duplicate position that I've explored. Soreturn zero. Otherwise, it's not been visitedyet. So I must be visiting it right now. SoI can add it. Nice. So I have my base caseslaid down. Now I'll need my actual recursivecode. So I'll explore my four neighbors. Bynow you should be familiar with this pattern.So go upwards, a row minus one column passon the same visited. So I'm going to exploremy up down left right neighbors respectively.And I do my recursively buffet theory, right.So what type do I expect back from these calls,they're going to give me back a number representingthe size of the island that my neighbor isa part of. But if my neighbor is part of somelarger Island, then I am too because we'reconnected right to our neighbors. And so Iwant to create the grand total of all of thesereturn values. So I'm going to create somesize variable, let's say let size, I'm goingto initialize it to one over here, it's goingto be one and not zero, because the one representsmy current position, my row column. And whateverthese calls return, whatever number I'm justgoing to increment my size by that number,like so. Then finally, I can return our totalsize over here. So that will do my depth firsttraversal, because it's recursive, but we'llalso tally up the size of this island region.Cool. So now that I have a working exploresize helper, let's use it in our main functionhere. So I'm going to get back a number fromthis call. I'll call it my respective size.And what's great about this logic is if Ihave a Island or position I've already seenbefore, and I encounter it again in this thisfor loop, then I would just return early becauseI would hit this base case, right? If somethinghas already been visited, just automaticallyreturn zero, because I've already consideredit, no reason to consider it again. But nowI need my minimization logic, right, I wantthe size of the smallest Island. And theytell us in the problem that we can totallyassume that your grid contains at least oneisland. So I think a great default value hereis to use positive infinity so I can set somewill say min size variable To be positiveinfinity, JavaScript, if I make it positiveinfinity, I know when I encounter any likevalid Island size, it's going to be less thaninfinity. And it should replace it. So nowI can do some min logic here and check. Allright, if the size of this island is lessthan the minimum size I have seen so far,then just replace that min size with thatisland. Then after I'm done with all of thesetraversals potential reversals, I'll returnmy mid size. So some classic patterns here.There's one nuance that we're not consideringhow to run the code, and we can debug it together.So it looks like we failed example. 00. Sothe very first example we expected to answerto, we accidentally gave back zero. If youlook at that first example, it's pretty obviousthat Yeah, the minimum size is two representingthis island over here. The reason we're givingback zero is according to our code. Let'ssee we're on like the very first iteration,I'm going to respond it, I know that row isgoing to be zero column is going to be zero,that means my position would be this w overhere. When I make the recursive call, andI pass along position 00, I know that it'sgoing to immediately return zero because thatposition is water. And I'm going to checkAlright, is that zero, less than infinityit is, so I'm going to replace min size withzero. But if I think about it, zero doesn'teven represent a real Island. If an islandhas a size of zero, then it's not an islandat all, it was a piece of water, right? Andso I want to add some additional logic hereto only actually look at nonzero quantities.So only do the comparison if that size isalso valid. So size should be greater thanzero, of course. And we'll want to add thesetogether. So let's try that again. Just alittle, little detail over there that we need.Awesome. And there we have a solution forthis minimum Island problem. So we've seenthis pattern a few times now, right or classicisland hopping logic. So when you think aboutislands are like connected components of agraph, this should be your first kind of goto algorithm. Alright programmers. So thatwraps up our course on graphs. I hope youlearned a ton during the course. I definitelyhad a blast making it Be sure to head to Shrutidotnet, where you can continue to practicemore graph problems, as well as explore anyother data structure algorithm topics. I'llsee you there.\n"