Graph Algorithms for Technical Interviews - Full Course

Aug 15, 2023

Graph Algorithms for Technical Interviews - Full Course

Learn how to implement graph algorithms and how to use them to solve coding challenges.

✏️ This course was developed by Alvin Zablan from Structy. Check out Alvin’s channel: / alvintheprogrammer

🔗 Learn data structures and algorithms: https://structy.net/

⭐️ Course Contents ⭐️
⌨️ (0:00:00) course introduction
⌨️ (0:02:23) graph basics
⌨️ (0:07:10) depth first and breadth first traversal
⌨️ (0:29:13) has path - https://structy.net/problems/has-path
⌨️ (0:42:11) undirected path - https://structy.net/problems/undirect…
⌨️ (1:00:44) connected components count - https://structy.net/problems/connecte…
⌨️ (1:13:29) largest component - https://structy.net/problems/largest-…
⌨️ (1:24:03) shortest path - https://structy.net/problems/shortest…
⌨️ (1:39:36) island count - https://structy.net/problems/island-c…
⌨️ (1:58:52) minimum island - https://structy.net/problems/minimum-…
⌨️ (2:12:05) outro

🎉 Thanks to our Champion and Sponsor supporters:
👾 Wong Voon jinq
👾 hexploitation
👾 Katia Moran
👾 BlckPhantom
👾 Nick Raker
👾 Otis Morgan
👾 DeezMaster
👾 Treehouse
👾 AppWrite

—

Learn to code for free and get a developer job: https://www.freecodecamp.org

Read hundreds of articles on programming: https://freecodecamp.org/news

Content

0.049 -> This course will help you learn what you need to implement graph algorithms and use them

5.1 -> to solve coding challenges. Alvin's dynamic programming course is one of the most popular

10.79 -> courses on our channel. And now he's back to teach you graph algorithms. Hey, programmers,

16.1 -> I'm Alvin from Structy. Welcome to our course on graphs. And in particular, this is going

19.939 -> to be about graphs for your technical interviews. Of course, graphs are a very common topic

24.199 -> when it comes to those technical interviews. And in particular, what I want to emphasize

27.949 -> throughout this course, is the handful of patterns that come up time and time again,

32.46 -> on those technical interviews. in just about two and a half hours, I'm going to give you

36.04 -> all the tools you need to basically cover I'd say about 80% of all graph problems. And

41.27 -> so what I have in store for this course, well, I think the key to victory for your data structures

44.91 -> and algorithms, and especially your graphs is to visualize things, right. So we're going

49.19 -> to do is trace through a lot of different algorithms, and be sure to understand them

53.1 -> at a high level. And that means going through different animations here, I think graphs

58.12 -> have a pretty bad rap for being a difficult topic. Because to a beginner, you can have

62.71 -> very, very different narratives around a problem, and not really understand. They're all really

67.09 -> based on a graph premise. So we're going to realize that a bunch of different things can

70.79 -> be understood as graphs. So when it comes to the prerequisites of this course, I'm going

75.11 -> to assume that you know nothing about graphs. But you do know how to code, right, so I'm

78.68 -> going to have the expectation that you understand some recursion. So as you work through the

83.09 -> course, and learn about different graph patterns, we're going to use those patterns to solve

86.39 -> some very classic interview problems about graphs, right. And I'm going to give you plenty

90.38 -> of opportunity to practice these patterns in different problems that we will be ready

93.79 -> whenever you have them on a technical interview. What I love about the topic of graphs is just

97.93 -> using a handful of different algorithms, you can cover the majority of graph problems,

102.95 -> right. For every graph problem that we cover, we're going to split it up into two sections,

106.45 -> section one is going to be about the approach for the video. So we're going to go over the

109.88 -> strategy and overall theory, and be sure to sketch out a nice meaningful picture. We're

113.84 -> also going to talk about the complexity of the algorithm in the approach video. Following

117.12 -> every approach, we're also going to implement the code of course, I'm going to be writing

120.23 -> all of my code in JavaScript, you'll be able to follow along in any language that you like.

124.41 -> So that means occasionally I'll be switching to my code editor where you of course can

127.55 -> follow along. We're also going to be sure provide links in description as well as links

132.06 -> on screen. That way you can formerly you read the prompts for every problem, as well as

135.96 -> look at the different test cases. Alright, I think that's enough introduction. For now,

139.37 -> let's hop right into the course. Alright, programmers. So let's jump right into the

142.85 -> course, I want to start by giving you some background about your graphs, we're going

145.9 -> to go over the graph basics that you need to start attacking problems in a technical

149.38 -> interview. So first off, what is a graph? A graph is really just a collection of nodes

154.43 -> and edges. So with respect to nodes, you can visualize them as typically just some circles

159.09 -> with some data inside of them. So I'll put some letter values in my nodes over here.

163.44 -> And when we refer to edges, that would be just any connections between nodes. So for

167.99 -> example, if there was a connection between A and C, it would look something like this,

171.63 -> right? What I can formally say is there's an edge between A and C, I can create many

175.84 -> edges between any nodes I want within this graph. Another word you might hear out in

180.48 -> the wild when it comes to describing nodes, as you might hear the word vertex being used,

184.17 -> right, they're really the same thing. In this course, I'll stick to the word node. And an

188.24 -> edge is just a connection between a pair of nodes. And that's really all a graph is at

192.19 -> a high level, where things get interesting is how we can use this graph framework to

196.17 -> actually solve a problem, right. So if you think of these nodes as just things and the

200.5 -> edges as relationships, a graph is grid describing the relationship between things. For example,

205.94 -> we can say that the nodes here are cities and edges would be roads connecting cities

210.41 -> are in a similar way, maybe our nodes here are courses, and then the edges represent

214.849 -> prerequisites. And so in the future, we're going to use graphs as a way to illustrate

218.92 -> and frame some narrative problem. Let's talk about this graph. In particular, here, I really

223.53 -> have drawn a directed graph. And that's because I have some arrowheads along the edges. That

229.099 -> would be a comparison to an undirected graph. So here, I have really the same structure,

233.819 -> except I don't have any arrowheads on the edges here. And that means that there is no

238.22 -> directionality to it right. If I look at the directed graph, let's say I was at the node

241.75 -> A, well, then I can travel to B or C, let's say I move to C. However, once I'm at C, I

247.36 -> cannot travel to a, I can only travel to E, right? That's because I have to obey the direction

252.551 -> of the arrow heads here. By take a look at my undirected graph, let's say I was currently

257.23 -> situated at the scene over here, that I do have the option of traveling to either a or

262 -> E, right? So if I traveled to a, that's all good, I can even travel back to C. So think

266.59 -> of as an undirected graph as a two way street. For now we'll just continue on with our directed

271.55 -> version. Let me also introduce some useful terminology we can use when talking about

275.46 -> the nodes in our graph. If I was currently situated at this a node, I can refer to B

280.379 -> and C as neighbor nodes. Alright, so a neighbor node is really any know that's accessible

285.749 -> through an edge, of course, obeying the direction of the edge. In other words, if I was currently

290.09 -> situated at the sea node, that I only have one neighbor of E, right, if I'm at the sea,

295.229 -> you know, then I won't consider a neighbor. Awesome. When you visualize graph algorithms,

301.22 -> you should really sketch a picture that looks just like this, right literally drop nodes

305.059 -> as circles and arrows as your edges here. However, when it comes to how we implement

309.669 -> this algorithm in some code, we're gonna have to represent it in a more programmatic way.

313.479 -> Right? So in my brain, I think of this image of like nodes and arrows between them. However,

318.55 -> in my program, I'm going to use typically an adjacency list, it's probably our preferred

323.12 -> way to represent and graph information, right. So depending on the programming language of

327.77 -> choice we're going to use typically, we would use some hash map data structure to represent

332.129 -> an adjacency list. Really, we're looking forward to using some constant time, I'll look up

336.83 -> data structure that has a key value pair mapping, right. So if you're in JavaScript, they'll

341.24 -> be an object, if you're in Python, they'll be a dictionary. If you're in a language like

344.779 -> Java, or C, you'll be using an unordered map. Looking at this hash map, I have drawn or

349.909 -> this adjacency list, the keys of this adjacency list are going to be every node in my graph,

355.58 -> right, so I just have all of the node values A through F laid out as the keys. However,

360.479 -> if you look at the corresponding values, the values are actually going to be an array,

364.33 -> right? So if I look at this very first entry, it says that I have a node of a and then in

371.139 -> the array of populated all of the neighbors have a that is a has two neighbors have BNC.

376.249 -> That's why I have this correspondence within my adjacency list. That holds true for every

381.8 -> entry within my adjacency lists. So for example, let's say look at the entry for e. So I go

387.54 -> to the spot and make j c list where the key is E, it only has a one outgoing edge to be.

393.11 -> That's why the array for he only has be inside of it. One thing to also note is even if a

398.669 -> node has no neighbors, it should still appear as a key within my adjacency list. For example,

403.36 -> if you look at the D, node D has no outgoing edges. That's why its neighbor array is empty.

408.02 -> However, it should still at least appear as a key within my adjacency lists, right, that

412.009 -> way, you can still know that the D node exists. So at the start of the course, will usually

417.33 -> be taking in adjacency list as the information to represent a graph, right. But as we sketch

422.569 -> through things on the whiteboard, we should be visualizing them using a nice picture like

426.38 -> this. Awesome. So let's actually jump into our first pair of algorithms. To me, the must

431.909 -> know algorithm for a graph is really going to be to do some sort of traversal on it.

436.36 -> Why don't we start by talking about a depth first traversal, something you may have heard

440.41 -> of before, right, now we're going to talk about the depth first traversal algorithm

443.79 -> that operates on a graph. So let's start by understanding at a high level what order a

449.099 -> depth first traversal would give you. So let's say I had some starting node, and I'm gonna

453.139 -> choose a as my starting node, right, so I'm gonna color it here in yellow. If I was following

457.599 -> a depth first traversal. Now that I've, you know, chosen as my starting point, I can either

462.039 -> hit B or C. Next, I'm just gonna commit to using B. So let's say I had the sequence so

466.809 -> far have a comma b. And at this point, if I was truly following a depth first traversal,

472.189 -> I must go deeper to the D node. In other words, I don't go to the C node yet. Cool, that would

478.87 -> be a true depth first traversal, right. At this point, now that I've bottomed out at

483.009 -> D, D is a dead end, right? I can't travel to F from D, because that would be disobeying

487.039 -> the arrowhead. And so now I can move to that other neighbor of C. And from here, the algorithm

492.679 -> would continue, right, I go from C to E, and then e to B. And technically, I would have

497.52 -> to double traverse some nodes like B and D over here. So overall, in this yellow coloring,

503.62 -> I have colored the full region that a depth first traversal would explore starting at

508.3 -> a notice that if you started at a it would be impossible to reach F. And that's kind

513.779 -> of normal, right? That's kind of why we use these traversal algorithms that can tell you

517.589 -> whether or not you can travel between some nodes. And we'll see that literal problem

521.919 -> later on. Right? So you're probably wondering, you know, exactly how do we implement this,

525.62 -> but for now, I just want to stay focused on the order that we got, right. So just regarding

529.99 -> our depth first traversal, we remember the first three iterations of the algorithm, we

535.13 -> hit the sequence of a B, D, right, that's indicative of a depth first traversal. Now

540.66 -> let's compare that to the breadth first Marion. So I'm going to lay down the same exact graph,

545.769 -> we're also going to start a traversal at the a node, but this time follow a breadth first

549.98 -> order. So I have a first and let's say, you know, I chose B as my next node when it comes

554.75 -> to breadth first traversal. It doesn't matter like which, you know, initial neighbor you

558.779 -> choose, so I'm just gonna choose B. But now that I've chosen B, if I was following a true

563.47 -> breadth first traversal, I must hit c next, right. And that's the main difference between

568.42 -> our depth first and breadth first reversals for the same graph, my depth first would start

572.81 -> a B, D, whereas my breadth first would start a, b, c. And so you're probably wondering,

578.5 -> is there any importance between this nuance right? When would I prefer depth first over

582.73 -> breadth first, or vice versa? Either a depth first or breadth first traversal would explore

588.25 -> the same exact nodes within a graph. However, it would explore them in a different order,

592.41 -> right? And this is more obvious to see when we have a larger graph with way more edges.

598.3 -> And so let's look at how he depth first traversal explores again, but this time on a much larger

602.089 -> graph, let's take a look at this one. So I'm going to choose some random node as a starting

606.519 -> point, let's say I chose this node in yellow, that was doing a depth first traversal, what

611.01 -> I'm going to do is, you know, pick a direction and travel in that same direction as far as

615 -> possible before switching directions. So let's say I move to the right, at this point, I

619.649 -> would have to continue moving toward the right, until I can't move to the right any longer,

624.06 -> at which point, I have to choose some new directions, let's say it was downward. I'll

628.19 -> keep doing that until I can't move downward anymore. And so I'd have to move to the left

632.079 -> now, now I'd keep chasing this single path in a very deep direction. So that's behavior

638.69 -> indicative of a depth first traversal, right, you're exploring one direction as far as possible

643.44 -> before switching directions. Let's compare that to a breadth first traversal. So let's

648.889 -> say start at the same node in pink, if I was following a breadth first traversal, it would

653.381 -> look something like this. From the starting point, I would explore all of the immediate

657.61 -> neighbors of this node, kind of in a circle like this. Now I just keep applying that behavior.

664.79 -> So as you notice about the breadth first traversal, is it'll tend to explore you know, all directions

673.029 -> evenly, right, instead of just favoring One Direction all the way through. That's really

678.04 -> the only difference between a depth first and breadth first traversal. Later on the

682.12 -> course, I'll bring up explicit problems where you might prefer one over the other. All right,

686.3 -> but for now, what I want to do is give you all the background you need. So you can actually

689.26 -> build this algorithm will kind of talk about things at a high level, consider this the

693.529 -> pseudocode, then, of course, we'll express it in some JavaScript code later on. So when

698.121 -> it comes to actually implementing in code, these two algorithms, the key is to understand

702.81 -> that a depth first traversal uses a stack, and a breadth first traversal uses a queue,

708 -> recall that a stack is something where you add to the top and remove from the top as

712.04 -> well, or is it Q is something where you add to the back and remove from the front, and

716.12 -> it gives you two very different orderings. That's really the only difference between

720.1 -> these two algorithms. So let's start by tracing through our depth first traversal, of course,

725.16 -> using a stack, so I'm going to use a slightly different graph. And to visualize my stack,

729.75 -> I'm going to use this bar to represent the bottom of my stack, obviously, for me, at

733.959 -> least I think of a stack as some vertical data structure. Cool. So let's say I just

738.589 -> arbitrarily chose a as my starting node to perform my depth first traversal, right, in

744.24 -> the long run, just want to print out all different node values within this graph. So what I'm

749.11 -> gonna do is I'm gonna take my starting node of a, and I'm just gonna immediately initialize

753.41 -> it onto my stack. So right now as the only thing on my stack, it's also at the top of

757.8 -> my stack. And now I can enter the flow of the main algorithm here, because I have a

762.18 -> stack, what I can only do is remove the top of my stack. So that means I pop off a from

767.05 -> the stack, and consider the a node, my current node being looked at, right? At this point,

772.639 -> let's say I print out a to my console. And from here, what I want to do is consider A's

777.329 -> neighbors, right. So if I look at the C node, what I should do is just push c to the stack,

782.589 -> then also push B to the stack, right. And it doesn't matter like in which order you

787.55 -> push these neighbors. If I want it to hit B first, then I'm going to push them second,

792.139 -> right? Awesome. That would end like my first iteration of this depth first traversal. Cool.

798.62 -> So at this point, I can look at my stack, and my stack still has some data on it. So

802.279 -> I should do is again, pop the top of my stack. So I'm going to pop and be off my stack. And

806.839 -> that becomes my current, I'm also going to print it out. At this point, I look at B's

811.579 -> neighbors, B has one neighbor of D and so I push d to the top of the stack. Notice that

816.689 -> because I have a stack D ends up on top of the C, right. And so now when I get to another

823.079 -> iteration, when I pop the top of my stack, I look at the D node as my current, right,

827.87 -> and I can print out D. And this feels good because so far, my print order would be a

833.389 -> BD, notice that I kind of pursued that single path deeply following a BD. But I have to

839.6 -> look at DS neighbors, I can take f and just push f to the top of my stack. next iteration,

845.329 -> my stack is still on empty. So I should do is pop the top F is now my current, I can

849.899 -> print out F, but f has no neighbors. So F isn't going to push anything else to the top

855.01 -> of the stack. Right? At this point, I get to this next pass, and I pop the top of my

860.31 -> stack. And that means C is now my current, I can print out CS value. And then I can look

865.47 -> at Sue's neighbors. And I just push e to the top of my stack. On this last iteration, I

871.37 -> popped up on my stack, he is now my current I print out he since he has no neighbors,

876.93 -> I don't push anything else to the top of my stack. And at this point, I've reached the

881.139 -> state where my stack is empty. And that means my algorithm is done right that means you

885.639 -> explored as far as possible within your graph. Notice that it might not necessarily be the

891.68 -> case that you're able to hit every node of the graph. And this particular example it

895.88 -> was possible though, awesome. So let's redo that trace using Our breadth first algorithm,

901.43 -> which means we just adjust things slightly. And we use a queue order. Remember that a

905.709 -> queue is a first in first out data structure, meaning things enter to the back, and then

910.189 -> they leave from the front. And so let's say I use this arrow to represent the directionality

915.149 -> of my queue, right. And I start the algorithm in the same way for my breadth first traversal.

920.17 -> Let's say I want it to begin at node A. So I just initialize my queue with a cool, so

925.98 -> I start by removing the front of my queue. So a becomes my current node, I can print

930.8 -> out a as well. And now I consider A's neighbors, right. So I consider B and C. If I wanted

937.129 -> to travel to B before C, then I should push B to my queue first, right, so I add B to

943.43 -> the back of my queue, right. And I should also add c to the back of my queue, right.

949.91 -> And that would actually end my first iteration. So now I look at my queue still has some stuff

955.509 -> on it. So I removed the front of my queue, that means B becomes my current. Of course,

960.759 -> I print out B. Now I consider B's neighbors. So I just look at the D node, and I push d

965.759 -> to the back of the queue, since D enters through the back and ends up behind the C, and that's

971.26 -> really important behavior. next iteration, I removed the front of my queue. So my current

976.959 -> is now see, right, I can print out see, and then look at sees neighbors of just E and

982.49 -> I add e to the back of the queue, which means that in the order of my queue, he ends up

986.99 -> behind the my next iteration, I removed D from the queue, and I print out the edits

993.5 -> neighbor of F to the back of my queue. next iteration, I removed e from the front of my

999.529 -> queue, print it out. Since he has no neighbors, he is not going to add anything else to the

1004.399 -> back of the queue. And of course, finally, f leaves the front of my queue, I print out

1009.35 -> F, F has no neighbors, at which point now my queue is totally empty. And since our queue

1014.24 -> is empty, that would be the end of our algorithm. Alright, and that's all there is to our depth

1018.57 -> first and breadth first algorithms, they're going to be the nice baseline code that we

1022.86 -> use to solve many different graph problems. I think that's enough theory. For now, what

1026.53 -> I want to do is now switch to my code editor, where you can actually implement these in

1030.27 -> JavaScript, hey, programmers, here I am in my editor, what I want to do is now show you

1034.57 -> how to implement those depth first and breadth first algorithms. So we'll start with the

1039.02 -> depth first. And my goal is really just to build a function that will print out all of

1042.88 -> my values in the graph, according to a depth first traversal, right, we're going to define

1047.64 -> this function depth first print, making an arrow function in JavaScript, it's going to

1052.56 -> take in the graph, which is going to be given as a nice adjacency list. And this is actually

1056.37 -> the same graph. Now last example we traced out, I'm also going to need to specify some

1060.9 -> starting node here, I'll call it a source node, we're going to begin the traversal.

1065.91 -> Starting at that node. Cool. And so we know inherent to a depth first traversal is going

1071.88 -> to be a stack. So I'll show you how to implement this iteratively, which means you need an

1076.01 -> explicit stack. For me in JavaScript, that's as simple as just using a JavaScript array,

1081.2 -> right? I'll make it empty at the start. And I can use this array as a stack, if I just

1085.99 -> commit to using operations that manipulate the same end of the array. In other words,

1090.62 -> if I just use push and pop, that will always manipulate the end of the array, right? removing

1096.05 -> and adding to the end of that array. What I want to actually be sure to do is I want

1100.271 -> to initialize the stack with my starting node, that is with my source node. Remember that

1105.05 -> like a node here is really just designated by some character. Cool. And when it comes

1110.6 -> to designing like the main loop for the algorithm here, do you want to keep running the algorithm

1114.45 -> while the stack is not empty? In other words, wall stack dot length is bigger than zero,

1119.97 -> that I have to keep running. That's very reminiscent to what we expressed on the whiteboard. So

1124.64 -> when it comes to performing like a single iteration of this depth first, what I want

1128.19 -> to do is remove the top of my stack. So if I do stack dot pop, that will remove the last

1133.48 -> item of an array, in this case like the top of my stack, and also return it to me. So

1137.46 -> I'm going to save that to a variable, I'll call it my current. And so this point would

1141.34 -> actually be a great opportunity to just print out that current. So I'll console dot log

1145.68 -> current, right? So looking at, you know, this example over here, since I initialize a stack

1152.01 -> to contain just the source note of a, on the very first iteration, this while loop, I would

1155.66 -> of course, pop out a, then I would print it out, right. And from that point, what I want

1160.39 -> to do is consider A's neighbors of B and C. So if I want to look at like the array associated

1165.8 -> with a, I can just key into my graph, right, cuz my graph is an object right now. So if

1171.06 -> I say graph, square bracket, current, right, if current is a, that means graph, square

1178.05 -> bracket current would give me back this array. I want to iterate through every node or every

1182.51 -> neighbor in that array. So I'm going to nest a loop here. And I say for let neighbor of

1188.11 -> that array. So if you're familiar in JavaScript, if you just use a for of loop, they'll iterate

1192.4 -> an order through an array. So now I'm hitting a neighbor as B and neighbors see. What I

1198.361 -> want to do with those neighbors is simply Push them to the top of my stack. So that

1202.72 -> will just be stacked up, push and push this neighbor. Awesome, I'm going to be sure to

1208.75 -> push every single neighbor that has. So sometimes I'll have two neighbors. Other times I'll

1213.12 -> have one neighbor, or even no neighbors. That's really all there is to implementing a nice

1217.8 -> baseline depth first print. Something that I do want to point out, my favorite way to

1222.83 -> implement this algorithm is to consider like processing your node, when it leaves the stack,

1227.59 -> not when it enters the stack. In other words, I usually write like my print statement, right

1231.93 -> after something is popped. And the thing that I pop is exactly what I print. Right. So let's

1237.12 -> go ahead and give this a run, see what we get. It looks like in my terminal, I got the

1243.2 -> order of AC e b df, which you'll notice is slightly different from what I expected from

1248.89 -> over here. However, this would be also a valid depth first traversal, we have to bear in

1254.97 -> mind is you know, depending on like the arbitrary order of values within the same neighbor's

1260.47 -> array, you could tend a different direction at first, right? Most important thing I look

1264.43 -> for when it comes to verifying a depth first is to make sure that I you know, chase the

1268.47 -> same direction before switching directions, right. So since I started out with a C, so

1273.26 -> I go a and then to a C over here, the next move would be going to E and that's exactly

1278.61 -> what happened in my code, right. And then once I hit E is actually a dead end. So then

1284.32 -> I can go on to my other lateral neighbor like B, right. And so I can contrive the same order

1291.66 -> expected here, if I just flipped this right. And so I put c followed by B. I'll give that

1297.37 -> around. They're both valid. depth first traversals. See what we got now. Cool, now I get the exact

1303.93 -> order of A, B, D, F, C. And really think about why that is, right. So let's say that I just

1310.34 -> popped out a from my stack. So I printed out a that's nothing fancy, right. And then from

1315.14 -> there, I start iterating through the array that's associated with a right, so on the

1319.89 -> first iteration, I iterate through C, right? If I push C on the stack, let's say this is

1324.59 -> the bottom my stack, by pushing on the stack, it's right here. Then followed by that I pushed

1329.39 -> B on the stack. Now B is on top. Since B is on top, I know like the next top level iteration,

1335.34 -> this while loop, I would remove B and that's going to be the next note I visit. And so

1339.01 -> they're really both depth for sure Russell's. Nice. So two things to note, you're definitely

1344.69 -> going to use a stack to implement depth reversal. And you can use the stack in a few different

1349.02 -> ways. Right? So here I'm using like an explicit like array as a stack. And I'm implementing

1353.08 -> this using some iterative code, right. So using a few loops, right, what you can also

1358.05 -> do is implement depth first recursively, because I know any recursion uses the underlying call

1363.54 -> stack. So let me show you how to implement that as well. And when it comes to, you know,

1368.65 -> having all these different tools in your arsenal, I would definitely practice both the iterative

1372.79 -> and recursive flavors. We'll see that later on in this course. So let's say I wanted to

1377.48 -> solve the same problem. But now recursively, it's actually going to be less code. So I'm

1382.87 -> going to have the same sort of arguments, I'm going to have the graph which is the adjacency

1386.71 -> list as well as a source node, consider like the source node as like your current location.

1392.32 -> So if I'm at some node, maybe the first thing I should do is just print out myself, right,

1396.66 -> print out this node, so I'll do is console dot log, this source node. And that feels

1401.79 -> good just from the get because when we actually do a top level call to this recursive function,

1407.01 -> they're passing in a as the source node. So I do want to begin a as a first note in my

1411.42 -> print, and then from there, I need to look at AES neighbors. Well, if you want to look

1415.44 -> at as neighbors like before, just key into the graph, adjacency list using that node,

1421.43 -> right, and this would give me an array of CNB. Now I just iterate through that array.

1425.9 -> So I'll say for let neighbor of that array. And at this point, what I want to do is now

1431.47 -> do the recursion, right, so I make a recursive call on each of these neighbors. So for me,

1436.52 -> that means just called depth first print, you give the same graph, right, the graph

1440.72 -> object doesn't change, but you should change like the source node. Now you want to pass

1445.4 -> in that neighbor as the source node. And you're going to make a recursive call for every neighbor

1451.5 -> in that array. And this would actually be all we need. Let's go ahead and just run this

1456.6 -> version. divider run over here. Looks like now we get the order AC E, B, D, F. And that's

1464.75 -> really again, another type of depth first print, right, not exactly this order, because

1468.79 -> this time we chased c first, right, we went a C, I want to get exactly this ordering and

1475.22 -> my recursion, then I would have to put in B first, really same sort of pattern. Now

1480.64 -> let's get that into the run. Good AB de FC. One thing I want to bring up about this recursive

1486.47 -> first is it has no explicit base case, meaning there's no obvious like, if statement that

1491.4 -> just like returns like you'd typically see in most recursion. That's because in this

1495.32 -> problem I have an implicit base case when a node like he is a dead end. All right, let's

1501.28 -> say my current source coming in is he, well, then when I iterate in this for loop, I'm

1505.99 -> iterating through this empty array, I mean to have zero iterations. If you have zero

1510.12 -> iterations, then you never make a recursive call. Right? That's the same thing as having

1513.89 -> a base case, right? A base case is really just a scenario where we don't have a recursive

1519.04 -> call. So that's how this code still works. Alright, so now you know how to implement

1522.91 -> depth first in two ways, right, iterated and recursively. And they both use definitely

1526.58 -> a stack. Let me now show you how to implement your breadth first, right as well comment

1531.3 -> out some of this code. Now we'll do a nice breath first, give myself some room over here.

1538.79 -> So for a breadth first, we want to solve the swan iteratively. And it's really only possible

1543.78 -> iteratively, right. So I know a breadth first traversal demands a queue, if you try to like

1548.51 -> implement a breadth first traversal using some recursion, and under the hood, there's

1552.51 -> some stack data structure, that's going to fight against the queue order that you want,

1556.06 -> right? So for breadth first traversal, you're always typically going to be writing some

1560.07 -> iterative code. So some loops, right? Let me define this, I'll say breadth first print,

1565.97 -> take in the full graph, adjacency list, as well as the source node, I want to initialize

1573.07 -> my queue. With that source note, again, the queue here is just going to be an array in

1577.75 -> JavaScript. So I'll say const q equals an array that begins with just the source node.

1583.24 -> Awesome. And I'm going to use this queue by just committing to two specific methods on

1588.22 -> my arrays in JavaScript. So if I use array dot shift that removes the first element of

1593.7 -> an array. If I do array dot push that adds to the last position of an Array. And using

1599.66 -> those two methods in combination would give me a nice cue, right, add to one end and remove

1604.16 -> from the other end. So like before, we're gonna have a while loop, we're gonna iterate

1607.36 -> while our queue is not empty. And so while queue dot length is bigger than zero, nice.

1613.15 -> And same thing as our iterative, you know, at first, you want to start by just removing

1616.83 -> the front of your queue. So I'll say q dot shift, that will remove the first element

1622.01 -> as well as return it to me. So I can save in a variable, I like to call it current,

1626.42 -> just like the whiteboard, right? And from there, maybe I'll print it out. So console

1629.4 -> dot log, this current node. And from here, just consider your neighbors, right. So if

1635.01 -> I key into my graph, using this current node, that gives me an array of its neighbors, I

1641.16 -> want to loop through each of those neighbors. So I can say four will say let neighbor of

1645.44 -> that array. And for that neighbor, I want to add them to the back of my queue. So for

1650.5 -> me, that would mean simply q dot push, I'm going to go ahead and push that neighbor.

1655.65 -> Awesome. So I remove from the front, and I add to the back. So that looks pretty good.

1661 -> Let's go ahead and give it a run. And actually, before I do that, I'm going to change the

1664.23 -> order of this, put the CNB. Again, doesn't really matter the relative order for neighbors,

1669.33 -> I just want this exact output, and we'll talk about why that is right. Give that a run.

1673.92 -> So I get ACB EDF just like I expected ACB EDF, right. So let's say you're on the first

1679.48 -> iteration of this breadth first print, I know that I would have just removed a because I

1683.54 -> initialized a on the queue, right? So my current is a and I print out a and then from there,

1688.24 -> I start iterating through this array, right. So on the first iteration, I have C, that

1692.57 -> means I put c into my queue, right? And then afterwards, I put B, if you put C and then

1699.95 -> B, that means C is at the front of the queue, which is why on the second iteration, I have

1704.45 -> C first, right? So that's how you can manipulate potentially the lateral order of a breadth

1709.29 -> first print. Awesome. That's all there is to this traversal algorithm, what I really

1713.5 -> want emphasizes, especially if you look at the apples to apples iterative code, you compare

1719.991 -> depth first or breadth first, it's almost identical code. You're really just changing

1724.28 -> how you access items in your array, right? You either pop or push or you shift and push

1731.47 -> harder than that the whole like structure of this code is identical, right? All right.

1735.77 -> So that's our introduction on depth first and breadth first for our graphs. In the next

1739.78 -> section, we're going to start to solve a problem, right, which will be really fun. I'm just

1743.46 -> utilizing this code as our baseline tool. And then that section also promised that start

1747.22 -> doing the analysis for bego of these algorithms. So let's jump back to that whiteboard. Hey,

1751.99 -> programmers, welcome back, right, and let's go over the approach for this has path problem.

1756.85 -> So in this problem, we're gonna take in an adjacency list representing a graph for this

1761.38 -> problem, and really all graph problems, you definitely want to visualize this one with

1764.2 -> a picture. And so what we'll do is we'll interpret each key of this adjacency list as representing

1769.13 -> a distinct node. And if I look at any particular list, I can see that this f node should point

1775.88 -> to G and I. And they do tell us in this problem that I have a directed graph. So I'm going

1780.23 -> to draw arrowheads on these edges here. So F points to G, as well as f points tie. And

1785.84 -> I'll create similar edges based on the information in the given graph. So we end up with an image

1790.72 -> like this, until they tell us that this is a directed graph that explains the arrowheads,

1794.59 -> but they also tell us that this graph is a cyclic. So if you're unfamiliar, a cyclic

1799.34 -> just means No cycles, that kind of begs the question, what is a cycle in a graph. So a

1804.84 -> cycle would be a some path through nodes, where I can end up where I want started. In

1810.15 -> other words, if I started at the a node over here that I can go to B, then from there,

1813.84 -> I can go to C, then back to a, and so on and so forth. So if I did a traversal, on the

1819.39 -> Sigma graph, I would get an infinite loop. And what they're saying is, our graph input

1823.57 -> is guaranteed to be directed. So it has arrowheads, but also a cyclic, so we don't have to consider

1828.57 -> any infinite cycles here. That being said, In this problem, we also want to take in not

1832.98 -> only the graph information, but also a source and destination node, we want to do is return

1839.06 -> true or false indicating whether or not we can travel from the source node to the destination

1844.04 -> node. In other words, is there a path that exists between those two nodes? For this problem,

1849.29 -> you can use either a depth first or breadth first search to actually solve the problem

1853.31 -> here, I'll trace through in this approach video, just the depth first search. But in

1857.45 -> the walkthrough, I'll be sure to code it up both ways. So let's say started at my source

1862.66 -> node, I know that if I was doing a depth first traversal, I can either choose the IRG, let's

1867.72 -> say happen to choose to G next. Now I have no choice, right? If I'm doing truly a depth

1872.27 -> first, I should go deeper to the H. So then I hit this H. And as I traverse through these

1876.83 -> different nodes, I need to ask myself if my current node is equal to my destination. So

1881.4 -> far, that hasn't been true. At this point, I bottomed out with my h node, I can't travel

1885.39 -> any deeper. So now I can move laterally to a node like I, at this point from I can either

1890.4 -> move to a K or a G, let's say by luck, I just happen to go to the G, this would actually

1895.12 -> bring me down a path I've explored previously, which we can optimize later on, but wouldn't

1899.62 -> be too much of a big deal. Eventually, if I continued this depth first search through

1903.86 -> the graph, I would end up at a node that matches my destination, at which point I can return

1909.27 -> true signifying that there must be some path from F to k, just doing a depth first search.

1915.6 -> And as we do this depth first search, it's really important that you obey the directions

1919.65 -> of your arrows. So I should never try to travel upstream. So that was a scenario where we

1924.55 -> were able to find a path from source of destination. That's why we return true. Let's reset and

1929.62 -> say that now, I should return false. Alright, so let's say my source was J. So I start at

1933.95 -> J. And I'm trying to get to my destination of F. If I start a depth first traversal,

1938.62 -> here, sorry, my j node traveled to the AI node. At this point, I can hit either the

1944.06 -> G, okay, let's say I happen to hit the k, this point of bottom now. So now I can move

1948.05 -> to the G. And then from there to the H. And at this point, there's actually nowhere else

1952.64 -> I can go, right. So if I finish my traversal through the graph, using either a depth first

1958.09 -> or breadth first and I never hit my destination, then I can just return false, right? It must

1962.75 -> be the case that there is no such path from my source to my destination. When it comes

1968.41 -> to implementing the depth first and breadth first reversals on this graph, it's going

1972.17 -> to be exactly what we're used to, you can either use a stack and solve it recursively.

1976.32 -> Or you can do it iteratively. And use a queue in which case you'd be doing the breadth first

1979.77 -> traversal. We talked about the complexity of this, let's say that n is the number of

1984.51 -> nodes of our graph, a common thing that you can also do with these graph problems is define

1989.49 -> e as the number of edges here and edges refers to a connection between two nodes, basically

1995.09 -> just the arrows. So if we use these two terms of number nodes and number edges, we would

1999.22 -> have a time complexity of our V o of the number of edges as because we would have to travel

2004.93 -> through every single edge of our graph. Here, the space complexity would be based on the

2009.51 -> number of nodes, right? If I solved it, recursively, or even iteratively, with some sort of a depth

2014.48 -> first stack, then the worst case, I would have to have every single node on the stack,

2019.57 -> right? Likewise, if I saw the eternity with a breadth first I would have every single

2023.5 -> node on the queue. So that's just one way we can define the terms for analyzing the

2028.68 -> time and space of this graph. Typically, for graph problems, another acceptable way to

2033.07 -> analyze the time and space of your algorithm is to just use a single variable and just

2037.27 -> define n as the number of nodes. That's because if you say n is the number of nodes, then

2043.19 -> we can also say that n squared would be the number of edges, or that big O. It's about

2048.47 -> the worst case. So let's imagine the worst case graph. Let's say I just had these nodes

2052.53 -> of ABC. Well, if I wanted to create as many edges as possible, how would I just create

2057.06 -> a single edge? Well, an edge is just a connection between two nodes. So you could just really

2062.88 -> draw an edge for every pair of nodes in your graph, something like this. And that's why

2066.93 -> we can say that n squared is the number of edges of any particular graph. And so if you

2072.44 -> just wanted to use n to define the complexity here, then you could say that your time is

2076.28 -> going to be O of n squared, and your space complexity would still be O of n. Do know

2081.56 -> that these are both two valid ways for defining the complexity for a very typical graph problems.

2087.89 -> That being said, I think this is pretty straightforward. Let's hop into the walkthrough video while

2091.649 -> we're actually implement both a depth first and breadth first solution for these. I'll

2096.28 -> see you there. Hey, programmers, Alvin here, right now. Let's go over Ah, JavaScript solution

2100.72 -> for this has path problem. And so we'll jump right in, we're gonna start by solving this

2104.44 -> one using a depth first traversal, which I know requires some underlying stack data structure,

2109.7 -> I'll just implement that using recursion. So I can leverage the call stack to get my

2113.79 -> ordering. And so I'm gonna solve this recursively, I'm gonna consider my source argument as like

2119.11 -> my current position during the traversal. And so I can have a base case in check. All

2123.48 -> right, if my source is equal to my destination, that I must have found the thing I'm looking

2128.2 -> for. So just return true. This base case signifies that I found my destination. So there must

2133.07 -> exist a path. And so I return true, always paying attention to the type that they want

2137.25 -> us to return for this function. Let's say it's not true, well, they need to keep looking.

2141.62 -> So what I should do is consider my current node, which is source, consider its neighbors.

2146.59 -> If I key into my adjacency list, I know that this is going to be an object. So I key into

2150.55 -> it using my source, that would give me an array of all of its neighbors. So for example,

2155.09 -> let's say it was staring at this one, if my current source was F, and I say graph square

2161.55 -> bracket, F, I would get back an array of gi. So now I want to look through the neighbors,

2166.67 -> right? So I can see over here is turned us into a loop and say for that neighbor of those

2174.42 -> neighbors, I want to traverse to them, which means I call recursively. Right call has path,

2180.77 -> keep your graph the same, but update your current position. Now I'm going to be situated

2185 -> at the neighbor. And the destination stays the same, right, always have the same goal

2189.42 -> to get to solving this one recursively. So think about what type of this is going to

2194.46 -> return, I know it's going to give back Boolean, right, it's going to tell me whether or not

2198.24 -> there is some path between my neighbor and the destination, right. So if there's some

2203.58 -> connecting point, or some connecting path between my neighbor and the destination, then

2207.68 -> I know that there must be some path from my source to the destination, because your source

2212.42 -> is definitely next to your neighbor, right. So there would be a path between all of us.

2217.07 -> And so what I'll do is, check if this recursive call returns true, I'll make it explicit here,

2223.42 -> maybe it's clear. And so if there is some path through my neighbor to the destination,

2229.52 -> then I can return true, just pass that true upward. Because once I find a path, you can

2234.901 -> just exit out and return that shoe all the way back to the top level of color. But let's

2239.87 -> say that this call returned false, that means that there is no path through my neighbor

2245.261 -> to the destination. But it couldn't be the case that some other neighbor is actually

2249.32 -> going to work out. And so what I don't want to do is just say like else return false,

2253.52 -> you should be able to immediately catch that code like this as suspect because there's

2257.15 -> no point of having a for loop then right? If in either case, you're always going to

2260.74 -> return, then you're never going to have a second iteration of this for loop, right?

2264.78 -> So if I don't find a path through my neighbor, so if this call returns false, then that's

2270.67 -> okay. Just continue on to the next iteration, and search through your other neighbor. that

2276.17 -> begs the question, Where should we return false, needs to be after the for loop? So

2279.88 -> only after I searched through all of my neighbors, and I never find a winning path? Should I

2284.25 -> return false, and that'd be our nice depth first traversal. Let's give that a test run.

2289.79 -> Awesome. There we have it. One thing to bear in mind here, we are leveraging the assumptions

2293.69 -> in the problem, right, they tell us straight up that the graph is going to be given is

2297.56 -> a sick like, so there are no cycles. So that's why in our code, we didn't really worry about

2301.62 -> getting trapped in an infinite loop. In our upcoming problems, we'll have harder grass

2305.48 -> to actually deal with that sick case. But for now, this is a good baseline solution.

2309.75 -> While we're here, let's also do a reference solution, which you know, by now should be

2316.81 -> iterated, right, there's no way to do like a breadth first recursively. And so I need

2321.28 -> to create my own queue. So I can create a queue, kind of in a pinch, I always just use

2326.59 -> an array in JavaScript, I'm gonna initialize that queue with my source on it. So I'm gonna

2331.97 -> refer to like source and destination, they're really nodes. But in the context of like our

2336.02 -> problem, they're really just given us strings, but they represent nodes, right? So think

2340.25 -> about the information they represent. I'm going to iterate while my queue is not empty.

2345.7 -> So while q dot length is bigger than zero, should be familiar code, very similar to our

2350.02 -> tree algorithms. And I start a single iteration of reference by removing the front of my queue.

2355.25 -> So I can say q dot shift some of the front, I can call that my current node that I'm traversing

2361.35 -> through. And now that something has left the queue, typically here is where I check, I

2366.11 -> can check. All right, if a thing I just visited, if that is my destination, then I can just

2372.44 -> return true, right, I found the thing I'm looking for. So there must be a path that

2376.31 -> connects my original source and my destination. Nice. But let's say this was not true. Well,

2383.03 -> then I need to consider its neighbors. So like before, look at the neighbors just key

2388.28 -> into your graph using the source like it's a graph, square bracket source. That gives

2392.22 -> me an array of all of the neighbors, all the neighbor nodes. That's what I want to do here

2397.35 -> is iterate through every neighbor Over there. And then I can just add them into my queue.

2404.78 -> So q dot push that single neighbor, and do be sure to implement your true breadth first.

2411.48 -> So you need to make things leave from one end of your queue, and you add to the other

2417.04 -> end. So this codes looking good. So you should realize how similar This is to our old like

2422.45 -> binary tree breadth first, except now we have to account for the fact that we could have

2426.03 -> like a dynamic amount of neighbors here, not just dot left and dot, right. So I'm just

2431.6 -> iterating through all those neighbors adding them, I need to wait to return false. And

2435.93 -> you guessed it, the move is after you finish this entire while loop, if your cube becomes

2440.5 -> empty, then you must have explored as far as you could. And if you never return true,

2445.49 -> and now you can return false, because it must be the case that there is no path between

2449.11 -> the original source and your target. So let's give this a test run will have a very similar

2456.24 -> time and space complexity. But this would be the code for all of my iterative fans.

2461.15 -> So here I'm getting a little error. Let's see what we did wrong here. So it looks like

2465.81 -> I timed out here. Let's see bug this one together, I had to guess that means I did something

2469.89 -> wrong getting trapped in an infinite loop. This condition looks okay, right q dot length

2474.75 -> greater than zero. And so here it is, must be the case that I'm not correctly iterating

2481.42 -> through the neighbors here, I just wrote source. Instead, I need to say current, because now

2486.47 -> I'm doing this iteratively, right. So whatever node has just left my queue, I consider that

2491.55 -> nodes neighbors and add them to be visited next through my queue. So let's give that

2497.29 -> a test run. honest mistake there. Cool. And there's our breadth first solution for this

2501.93 -> has path problem. So what I want you to do is practice both the depth first and the breadth

2506.19 -> first, like you expect, we're going to do a lot of graph problems coming up. And depending

2510.77 -> on you know what the problem is asking sometimes will prefer one type of algorithm over the

2515.27 -> other. So it's really important that you practice both of these algorithms. Now, all the problems

2519.69 -> are relatively easy. So practice this, give it a shot on your own. And I'll catch you

2523.421 -> in the next problem. See you there. Hey, programmers, Alvin here, right. Now let's go over the approach

2527.52 -> for this undirected path problem. So we'll jump right in. In this problem, we're going

2531.4 -> to be given an edge list for a undirected graph. So if I are familiar with the terminology

2536.48 -> here, really what we're saying is every pair and this edge list represents a connection

2540.76 -> between two nodes. For example, if I look at the first edge, and the list, I see i comma

2545.61 -> j, that means that there's a edge or connection between i and j. And since this is an undirected

2550.82 -> graph, not only can I directly travel from i to j, but I can of course, move from j to

2555.91 -> i. So it really represents a connection in both directions. And so as we start to attack,

2560.79 -> this problem we'll want to do is actually convert this edulis into a more favorable

2564.76 -> format, like an adjacency list. That's because typically, when we perform our traversal algorithms,

2569.78 -> they work best on an adjacency list form. So let's start by doing that conversion here.

2573.95 -> And I'll actually be pretty easy to code up. So I want to basically generate a graph where

2579.11 -> I have nodes as keys, I want them to point to a an array of their neighbors. For example,

2585.71 -> if I wanted to convert the first edge into an adjacency list form, what I can do is create

2590.54 -> keys for i and j. Now that I is a neighbor of J, and also j is a neighbor of I, so I'm

2596.28 -> going to populate those neighbors respectively. Now just follow this process for another edge.

2601.29 -> So if I look at the edge, k comma i, I need to create a new key for K. And I'm going to

2606.38 -> populate that with I and then for the existing key of I, I just add k into that collection.

2611.22 -> So do bear in mind, the most important thing about this conversion is because we know that

2615.32 -> the graph is going to be undirected, whenever you put a connection within your graph, make

2620.971 -> sure that you have the inverse connection. So if I have an edge from k to AI, they also

2626.09 -> need to have information for it. Okay. And this process would just continue for the entire

2631.99 -> list of edges. And by the end of this conversion, we'll end up with an adjacency list just like

2636.68 -> this. And now we're ready to perform our main algorithm. When we go through the code walkthrough

2640.96 -> for this, I'll show you in depth how you can actually create this adjacency list. And so

2645.86 -> when we want to actually come up with a traversal algorithm to solve a graph problem, it really

2650.27 -> helps if you actually visualize the shape of your graph. So actually want to visualize

2654.77 -> this in terms of nodes and edges. That means a bunch of circles and lines between them.

2659.29 -> If you drew out a nice picture for this graph information, you would end up with a diagram

2664.02 -> like so. And so we'll go through the rest of this approach video just referencing this

2668.48 -> diagram. Something important I want to bring up at this point is for this graph, a very

2673.98 -> common case we'll have to handle is what if your graph has a cycle. And that's especially

2678.63 -> true for your undirected graphs. And so just for the purposes of this approach video, I'm

2682.91 -> going to add an additional edge just so we can talk about an explicit cycle. So I'm going

2686.95 -> to add one new edge from k to J. Cool. The reason is now there's a nice big cycle of

2693.23 -> length three highlighting in red right now. And this cycle is important to watch out for

2698.22 -> because if we don't do any special handling Then we may get trapped in an infinite traversal.

2702.77 -> So imagine I started at this keynote, and next I moved to J, then I would move to i,

2707.33 -> and then back to k, and then back to J, and then I, and so on. So now it gives me a cycle,

2712.36 -> we'll have to guard against that. And so I can have a cycle of three nodes here, right,

2716.67 -> and you can really have a cycle of basically almost any size, as long as it's more than

2721.07 -> one. So for example, if I took a look down here, notice that my graph actually contains

2726.4 -> technically like two separate islands, but we would consider them as just one giant graph,

2730.99 -> right? So I've got the small island of O and N, they actually form a trivial cycle, right?

2735.97 -> If I started traversal, at o. From there, I can move to n. And because I know that the

2741.29 -> edge between o and n is bi directional writes an undirected graph, that means I can travel

2745.64 -> back to O, and then back to n. And this would give me cyclic behavior. So have to watch

2750.801 -> out for all types of cycles in this problem. So in the context of this problem, not only

2755.13 -> are we given a graph, we're also going to take in a two nodes. So let's step through

2759.59 -> an example where I want to return true or false, is there a path between I and L. So

2764.33 -> I'm going to mark those in my graph Israel. So I'm going to start at the notify. And to

2769.71 -> solve this one, you can use any type of traversal. So either depth first or breadth first, I'll

2774.57 -> step through explicitly the depth first traversal. Right. Now, in order to avoid any infinite

2778.56 -> traversals, I want to mark my nodes as visited as I travel through them. So not only do I

2783.56 -> situate myself at this source note of I, but I'm gonna mark it as visited. And you can

2788.51 -> implement this like marking a visited pattern. And a few different ways. When we code this

2792.72 -> up later on, we're probably going to use a set to represent what we have visited. But

2797.131 -> for now, I'll just check them off in my diagram. And so in my diagram, if you see a checkmark

2800.88 -> next to a node, that means that I already have visited it. So since I'm at this node

2804.681 -> of I want to move to its neighbors, so I'm gonna move to the neighbor of J. And I'll

2808.81 -> also be sure to check it off as visited. At this point, I can move to one of Jays neighbors,

2814.119 -> let's say I move to k. And I'm also going to mark it as visited. Now then Matt K, I

2818.86 -> can move to a few different neighbors, I could either move to I LRM. Let's say by chance

2823.96 -> I chose I, I once I get to this, I know, I'm immediately going to be able to see that,

2828.82 -> oh, I visited this node previously. So what I should do is not travel through it again.

2834.86 -> Instead, I should go back to the K, right, because this eye node is already visited.

2839.68 -> And that's where I actually avoid the infinite loop. So instead, I moved to some of Kay's

2844.14 -> other neighbors, let's say I chose the L. At this point, I would mark it as visited.

2848.44 -> If I do a quick check, I can see that this note I'm at L is also my destination node.

2853.82 -> So I must have just found a path between my source and the destination. So at this point,

2859.1 -> if I find my destination, I can just return true, which was a pattern we spoke about in

2863.87 -> a previous problem, the only additional criteria we need is to mark nodes as visited. That

2868.94 -> way, we don't get trapped in an infinite loop. And that's only going to be needed if we have

2873.1 -> cycles in our graph, which if they don't give us any assumptions we should always guard

2876.89 -> against. So let's take a look at another example. Let's say I had a source of K. And my destination

2882.1 -> was Oh, just looking visually in the graph, you can already see that there's no way to

2886.47 -> get from k to O, because they're disconnected, right, they're on separate islands both step

2891.13 -> through the algorithm regardless, so I'm going to start at K gonna mark it as visited, I'm

2894.98 -> going to visit some of Ks neighbors. So I can move to i, then I can move to J. And then

2900.54 -> at this point, I would move back to K and really make sure they don't explore any of

2904.64 -> Ks visited neighbors, so I don't move back to I right, instead, I should move to an unvisited

2910.4 -> neighbor, like l market is visited, then I only have one other node to visit, which would

2915.3 -> be this m node. And at this point, I've actually exhausted this full graph region, right, there's

2921.08 -> nowhere else I can go. And once I finished my traversal, if I never find my destination

2926.63 -> node, then I can just return false, right? It must be the case that there is no path

2931.48 -> that exists from my source node to the destination node. That's really all there is to this algorithm.

2938.03 -> Let's talk about the complexity. If we say that n is a number of nodes, let's also define

2942.85 -> that he is a number of edges. Like we said previously, this is something typically acceptable

2947.43 -> to do for our graph problems. I know that the time complexity is going to be roughly

2952.39 -> of the number of edges. And my space complexity is going to be O of n that is the number of

2957.08 -> nodes. I think it's worth stepping through, you know what this complexity actually means,

2961.7 -> you know, big O refers to the worst case. So let's think about a worst case graph that

2965.54 -> we can have. And there are a few different graphs that you can kind of design and think

2968.75 -> of, I'll just show you one example. So let's say I was given a graph like this, right?

2974.32 -> Notice that although z is kind of on its own island, all of these nodes that is a three

2979.2 -> as well as a C note. They're all members of the same graph. So let's say I wanted to figure

2984.57 -> out is there a path between A and z. So if I did my traversal algorithm from here, I'll

2991.49 -> start at a then I move to B, and then to C, and then to D, and then to E. At this point,

2997.48 -> I've covered all of the edges in the graph. Remember that the edges are the arrowheads

3002.33 -> here, because I have to travel through every edge of this graph. That's why we said the

3005.13 -> time complexity in the worst case is going to be o of E, right o of the number of edges.

3010.98 -> and here we can say the space complexity is O of n. Because if you're doing this with

3014.619 -> either a depth first stack, or a breadth first queue, in the worst case, you would have to

3019.83 -> add everything you visited, or that is all of the nodes onto your stack or queue. That's

3025.44 -> why we say for regular graph traversal algorithms, we have a time complexity of o v, and a space

3030.33 -> complexity of O of n. All right, I think we have the approach for this algorithm down

3033.83 -> pat. At this point, I want to join me in the walkthrough videos, where we can actually

3037.55 -> see how to implement these visited patterns in some code. I'll see you there. Hey, programmers,

3043.88 -> Alan here, right. Now let's go over a JavaScript solution for this undirected path problem.

3048.95 -> So we'll jump right in, just like we said, in the approach video, there's going to be

3052.09 -> a two parter. First, we're going to convert our edge list into an adjacency list. That

3056.95 -> way, it's easier to do a classic traversal through it. So I'm going to pretend I had

3061.37 -> a helper function here. That gives me back an adjacency list. I'll call it graph. And

3065.65 -> I'm going to call this helper function, we'll say build graph. And if I pass it, just all

3071.109 -> of my edges, I want it to do that conversion for me. So let's work on that helper function

3075.68 -> right now. And then we'll jump back to undirected path. So I'll create my build graph function,

3083.35 -> just going to take in the edges, right. And I know I want my adjacency list to be in the

3089.04 -> form of a plain old JavaScript object. So create that graph object here. And I'm going

3095.43 -> to return it by the end just like this. And what I want to do is fill up this graph with

3102.869 -> information from the edges. So I'm going to iterate through every edge. So for let edge

3106.859 -> of edges, so iterating, through every single edge, I know a single edge would be a pair.

3111.78 -> So I'm just gonna de structure out of that, maybe just my two node identifiers, we'll

3117.24 -> call them a and b, from the edge. Nice. What I want to do is now initialize these nodes

3124.3 -> as keys of this graph object. So a would be something like this, I note or this k node,

3131 -> right. So what I'll do is check if A is in my graph, I think really clean up this code,

3138.68 -> we better if I check if it's not in the graph. So if the a node is not in the graph, then

3144.6 -> what I can do is initialize it in the graph. So use it as a key and assign it to be an

3148.88 -> empty array. And I'll do the same for B over here. Right, so I'm initializing A and B in

3155.6 -> the graph if they don't exist, and once I do that, then I can safely just add neighbors

3161.13 -> into their their edges, right? So I can say, the graph square bracket a dot push B. So

3169.02 -> now I'm saying that right, B should be a neighbor of a, but I know that this is an undirected

3172.99 -> graph, right? So that should be symmetric. In other words, then make sure you push a

3179.29 -> into the neighbors of B. So it's really important that you notice that this is an undirected

3184.78 -> graph. So your adjacency list needs to be symmetric in that way. So if a is in B's neighbors,

3190.63 -> B should also be an A's neighbors. So that's looking pretty good. Let's go ahead and see

3195.8 -> how that graph looks just with a little little side test here. So I must steal maybe this

3203.02 -> snippet, get that full snippet here, I could just run it manually love to make sure I can

3210.45 -> test these little helper functions before I use them. So we'll give this a run, we should

3213.69 -> just see the adjacency list form of these edges here. See how it looks. So that looks

3222.07 -> pretty good. So I'm seeing that all right, I is connected to J and K. Right? And that

3228.491 -> looks correct based on these edges. Awesome. And I'm also want to make sure that it's symmetric,

3233.4 -> right. So if i and j are over here that I should have JNI over here as well, right,

3238.31 -> it should be a two way street. Alright, now let's work in our real algorithm here, which

3244.33 -> would be some sort of traversal. Now that you have a nice adjacency list, you can do

3249.9 -> either a breadth first or a depth first traversal. I'm going to implement I think, a depth first.

3255.15 -> Typically for me, it's just easier to raise push if I do it recursively. And so I'm going

3260.39 -> to pretend I had a function called has path, it's going to take in my graph now. And also

3266.79 -> a start node and an end node. So I want to find a path from node A to node B, of course,

3272.55 -> I'm going to assume that this function returns a Boolean. But of course, I have to write

3276.75 -> that function for myself. So stay organized in our code, we'll say has path. I'm going

3281.7 -> to take in the graph as well as node A and node B. And I think a better name for these

3288.38 -> arguments as I'm doing this recursively. Let's call this one source and this one destination.

3294.14 -> So over time, we're going to call recursively and update this source node. And that should

3297.89 -> be a familiar pattern to some other problems resolved. Recently. So think about my base

3302.48 -> case. All right, I know that I've has successfully found a path when my source is equal to my

3307.68 -> destination node, if that's the case in return true, because I just found a path. Otherwise,

3312.44 -> I have to keep looking. So I should be able to look through the neighbors of my source

3317.38 -> node. So I could say graph square brackets source, right? Remember that any point through

3321.41 -> this recursion source represents my current position. If I say graph, square bracket source,

3328.109 -> let's say source was I, I'd be accessing all of ies neighbors, right? So I want to do is

3333.14 -> really iterates for let neighbor and, or rather have graph of source. So if sources I on the

3342.891 -> first iteration neighbor would be j, second iteration neighbor might be K. And for each

3347.8 -> of my neighbors, I want to travel to them. So call has path, you can keep your graph

3352.87 -> argument the same needs to change your source though now you're situated at your neighbor,

3357.3 -> and your destination is fixed, or you're always trying to get to the same exact node. I'm

3361.51 -> gonna think about what type this returns I know this is going to tell me Boolean, right?

3364.869 -> True or false? Is there some path from my neighbor to the destination, I'm going to

3369.52 -> check. All right, if that call, returns true, I'll be explicit here, then I've just found

3376.03 -> a path. So just return that true, right, pass it all the way back up. And kind of the logic

3381.861 -> that we form here is, I know that by definition, source and neighbor are definitely connected.

3388.119 -> So there's definitely a path between them. They're connected by a direct edge. So if

3392.351 -> my neighbor has a path to the destination, then I know, then the source also has a path

3397.61 -> to the destination. Awesome. And so after this for loop is done running, let's say we

3403.78 -> never find that any of our neighbors make a winning path, then means I finished this

3410.3 -> for loop without ever returning true, which means that I can return false right must be

3414.98 -> the case that this source node does not have some path to destination. So I think we can

3422.03 -> go ahead and give this code a test run. If you watch the approach video, you'll notice

3426.241 -> that there's something important missing from this code. But we'll just run it and show

3430.28 -> you how to fish here. So here I'm getting an error edges is not defined what I do horribly

3436.15 -> wrong, line 34 months ago, line 34 over here. So got to take out this call, don't need that

3443.25 -> anymore. That's on me. Let's get that test run. So that was not the error I was expecting.

3450.53 -> I am expecting some sort of an infinite loop, though. Perfect, I'm getting maximum call

3456.26 -> stack size exceeded. So I got like an infinite recursion really. And that's going to occur

3461.1 -> because we didn't account for the case where we have cycles in our graph, right, we need

3465.451 -> to avoid that. Because if I have a cycle in my graph, I'm never going to hit any of these

3469.96 -> base cases, I'm just gonna keep traveling around in a circle. And if that's unclear,

3473.71 -> make sure you watch the approach video, right. And so like we said, the move here is to add

3478.46 -> some sort of data that shows where you've been previously. Typically, the way we do

3483.6 -> this for our graph problems is to track some visited set. So when I make my top level call

3490.22 -> to this house path, I know that that is the actual function that does that traversal,

3494.24 -> I'm going to pass along a new argument here. And I'll make it a new JavaScript set. So

3500.23 -> if you're unfamiliar with sets, and JavaScript, they're really just a collection of items.

3504.51 -> And what's really great about a set is in o of one time, I can add something into the

3509.06 -> set. And I can also check for something within the set is going to be very, very quick for

3514.57 -> our traversal. I don't want to use something slow like an array, because to do a lookup

3519.15 -> or a check within an array, that would actually be O of n time, or it's for a set, it's o

3523.721 -> of one. So I'm going to make a new argument here to receive a column visited. What I want

3530.33 -> to do is all right check if my source node is already in the visited set to do that in

3535.849 -> JavaScript I can check visited out has. So if the source node is inside of the visited

3541.96 -> set, then I could return false here, right, there's no reason to travel through this node

3547.44 -> anymore. Because if it's an visited then I must have traveled at previously. And this

3550.64 -> is how I can avoid an infinite recursion can also move this line downward if I wanted to.

3557.1 -> And let's say that I make it through this if statement. So that means that all right,

3561.88 -> this node source has not been visited. But I'm visiting it right now. So I need to do

3566.82 -> visit a dot add source. So this expression checks if source is in visited, and this expression

3574.23 -> adds source to the visited set. I want to change a few other details here. Make sure

3579.44 -> that you pass along the same visited set through all of your recursive calls over here. Because

3584.251 -> you want this visited set to be like global for the entire traversal right I need to know

3588.47 -> exactly where I've been in the past. And once we have that in place, that should be everything

3594.3 -> we need to prevent any any cycles from giving us infinite recursion here. Let's give it

3599.891 -> a test run. Awesome. There's a solution for our undirected path problem. So important

3606.98 -> things to take away here do consider this problem, a two parter right? phase one is

3611.4 -> really straightforward, just converting an edge list into an adjacency list, which is

3615.31 -> actually an important skill to practice. Because when it comes to, you know, some problems

3618.75 -> you'll face in the wild, they are all going to be basically graph problems. But sometimes

3623.54 -> they'll give you the graph and like a different format, and you can always convert into a

3626.87 -> format that you're comfortable with. And from there, we have a really core pattern of just

3631.29 -> doing a traversal through a graph, but also guarding against infinite loops, right. And

3636.19 -> to do that, we just use some sort of a visited set. Hey, programmers, welcome back right

3642.98 -> now want to go over the approach for this connected components count problem. So in

3647.11 -> this problem we want to do is take an adjacency list representing an undirected graph. As

3651.62 -> always, with any graph problem, you want to start by visualizing the actual graph. And

3655.05 -> so if you took a picture of this information, it would end up looking like a graph with

3658.96 -> this structure. The first thing we should notice about this visual graph is that a has

3663.31 -> multiple connected components. So for example, I can look at this component in pink spanning

3668.77 -> just the one and two nodes, I can look at another component spanning the four or 5678

3673.88 -> nodes. And finally, a third component just covering the three node. And that's why we

3678.74 -> say that your result for your function here should be three, right? Because there are

3683.2 -> three different connected components. So let's come up with an algorithm we can use to count

3687.57 -> the components, we know that a general counting algorithm is going to use some variable, and

3692.38 -> we'll initialize that count variable to zero. And the trick here is to use a combination

3697.359 -> of both some standard graph traversal code, maybe a depth first as well as some iterative

3702.43 -> code. So I'll do along the left hand side is just list out all of my different nodes.

3708.11 -> And what I'll do is start by iterating, through every node of this list. And what I'm going

3713.95 -> to do is when I'm currently at some note of this iterative list, I'm going to start a

3718.38 -> traversal at that node. So right now starting at the node of one, I begin, let's say a depth

3724.22 -> first traversal, you can really implement this pattern using either a depth first or

3727.78 -> breadth first. So let's say I start at the one node over here. What I should do now is

3732.4 -> continue this traversal as far as possible, that's the key to victory here. So from this

3738.01 -> one node, I can move to a neighbor of two. And of course, as I travel through these nodes,

3742.92 -> I want to make sure that I mark things as visited, so I can avoid loops. And marking

3747.599 -> things as visited will also ensure that we don't double count any components here. Once

3753.69 -> I hit that to note, I've actually completed this full component, there's nowhere else

3757.869 -> I can explore. So at this point, I should increment my count by one. So whenever I complete

3764.33 -> a new traversal on some region of the graph, I need to increment my count. At this point,

3770.3 -> I now fall back to my iterative code on the left hand side, and I iterate through the

3775 -> next node. So I now look at node number two. If I take a look at node number two, I see

3780.33 -> that I already have it marked as visited. So that means I don't need to start a traversal

3785.68 -> at that node. So effectively skip the two and keep the count the same. next iteration

3791.359 -> I have a three, three is unvisited right now. So I should begin a new traversal starting

3795.64 -> at this three node, which means I just mark it as visited. And since this three is a singleton

3800.54 -> node, right, it's not connected to anyone, I would actually complete their traversal,

3804.15 -> just on the three node. At this point, I've completed a traversal. So I increment my count

3808.95 -> by one. So now I have a total count of two, I fall back to my iterative code. So I moved

3814.07 -> from the three node to the four node. And I see that this four node is unvisited, which

3818.72 -> again means I must begin a traversal from this four node. And I'm going to expand this

3824.69 -> traversal. Starting at four as far as I can, before I go back to my iterative code, right,

3829.51 -> so I'm going to explore the six, explore this five, explore the seven, and finally explore

3835.31 -> this eight. At this point, I've completed a traversal. So I can increment my count up

3840.49 -> to three. And then I have to continue and fall back to my iterative code. So look at

3844.81 -> the five node, I see that the five note is already marked as visited, so I don't start

3848.5 -> traversal. And I see that the six node, same thing don't need to start traversal seven

3853.07 -> note already visited, eight nodes already visited. At this point, I would be done with

3857.98 -> the entire algorithm. And there's my final count of three. So a few interesting mechanics

3863.25 -> here, right, you're going to need to definitely implement some code or some function that

3867.53 -> does a traversal through some component as far as possible, then you also need some iterative

3873.44 -> code just to potentially begin a traversal at every single starting point. And what you

3879.091 -> want to do is be sure to mark nodes as visited as you traverse them, because only when you

3883.34 -> marked a new node as visited and complete that traversal should you increment your count.

3888.39 -> You're probably wondering the exact details of how we implement this in some code, but

3891.74 -> don't worry, you'll realize that it's really just a spin off of our previous graph algorithms

3895.67 -> in the walkthrough video, but for now, we see that n is a number of nodes And he has

3900.52 -> a number of edges like usual, we know that this is really just traversing through the

3904.381 -> entire graph. So we can say the time complexity is just o v, and the space complexity is O

3909.19 -> of n, right, depending on whether you do a breadth first or depth first, you're going

3912.88 -> to use that space, then in terms of your stack or cube. And we can also consider using the

3917.619 -> space within our set if you use a set to mark your nodes as visited, but overall, it still

3922.94 -> will lead to a linear time and linear space solution. Alright, I think I'm ready to code

3927.2 -> this one up. I'll see you in the walkthrough video. Hey, programmers, Alvin here, right,

3932.71 -> now let's go over a JavaScript solution for this connected components count problem. And

3937.12 -> so we'll implement exactly the strategy we spoke about in the approach video. So make

3940.421 -> sure you watch that first, we know that this is going to require really two different mechanisms

3945.59 -> are going to need our interactive code just to hop to different connected components.

3950.55 -> And we also need some traversal code to just explore some single component as far as possible.

3957.69 -> And so what I'll do here is let me start with the iterative code. So I need to begin a traversal

3964.44 -> at every potential node. So I can say for let node of my graph really say in my graph

3971.72 -> here, because for this problem we're given looks like JavaScript objects. So if I say

3976.849 -> for let node in graph that would give me each of these keys like 015, and so on. And so

3982.98 -> for every node of the graph, what I want to do is begin a traversal. So we're going to

3988.48 -> assume I have a function here, I'll call it explore. I'm gonna pass in, of course, the

3993.2 -> graph, as well as that node. And what I want that function to do is do like a, we'll say,

3998.31 -> a depth first traversal, from that node as far as possible, right, so probably going

4003.831 -> to need to add more logic into this main function. But for now, I think it's about time to actually

4008.36 -> flesh out explore. So I'll choose to do this explore method recursively. So we'll define

4015.18 -> explore, it's going to take in a graph, as well as my current node, I'll just call it

4020.17 -> current, right. And then from there, I want to solve this one, using a depth first. So

4027.63 -> recursion is fine. And not much to do here, but really go through my neighbors want to

4032.599 -> iterate through every neighbor of this node. So I can say like neighbor of graph of current,

4038.29 -> I recall that graph would be an adjacency list. So if current is spread this out. So

4046.13 -> if current was a node like eight, then on the first iteration neighbor would be zero,

4051.57 -> next iteration neighbor would be five. So here, I'm just going through all the neighbors

4055.66 -> of my current node, I just need to not traverse to them. So I can call explore, pass along

4061.2 -> the same graph, that doesn't change. But now my new current node would be that neighbor,

4068.349 -> just like that, and this will perform the baseline of just the kind of depth first traversal.

4073.89 -> But we need to also mark things as visited, like we said, in the approach video, that's

4077.43 -> a really important a part of the solution. And I want this like visited set to be global

4084.44 -> for my entire traversal. So I'm gonna have to create it, maybe my main function over

4089.28 -> here. So I can create my constant visited, make it a JavaScript set, because JavaScript

4094.839 -> sets off for me O of one lookup, and o of one addition, I can pass this visited set

4100.489 -> my reference until all of these calls over here. So I know I'm gonna receive visited

4104.94 -> over here now. Now I want to actually start using visited. So a few things to note, right,

4111.349 -> I definitely want to use visited to prevent cycles, right? That's one of the main reasons

4115.449 -> we always had visited to our graph traversals. So some familiar code here. If I've already

4120.719 -> visited this node, so if visited, has this current node, then nothing much to do here,

4126.889 -> maybe just return false. Later on, we'll see. The really cool trick we use here by returning

4133.42 -> false, right, actually serves two purposes. return false because this might be a cycle.

4139.839 -> And then I need to make sure that I pass as visited set along over here as well. Nice.

4144.859 -> And let's say that we have a current node that is not visited. So this statement is

4149.009 -> false. Well, then, it seems to be that we're visiting this node right now. So now we should

4153.159 -> add it into the visited set. Nice. And then beyond that, we need to make sure that our

4160.69 -> explorer function is consistent in its type, right? So I'm going to have my explorer function

4166.329 -> do is it's going to return true whenever it explores like a new node return true. So if

4172.969 -> you take a look at this code, for my function to hit this line 17 return true, then it must

4180.48 -> be the case that it has already finished exploring all of its neighbors, right, because I know

4184.71 -> that this for loop does the job of exploring all of the neighbors, right? So only after

4189.719 -> all of those neighbor calls returned. Will I return true? And that must mean that I've

4194.9 -> explored this component as far as possible. Right? And that seems good to go. And what

4202.239 -> I can do is now in my main function, when I call explore it, now it's going to give

4206.639 -> me boolean data, right? If it's exploring a new island, or a new component, it's going

4211.099 -> to return true. So I can check. All right, if explorer returns true, then that's a new

4217.61 -> component. So I can probably increment some count here, I should have created. So I'll

4221.84 -> say 11, counts equals zero, I'm going to increment that count, when I find a new component and

4228.659 -> plus equals one by the end, I should of course, return that counts. And what you'll notice

4234.65 -> is, for scenarios where we, let's say iterate into a node that we already explored, when

4241.989 -> I make this call, I know that that call is going to return false, because if something's

4246.48 -> already explored, it would have been added to visited. So that's why I'm using some Boolean

4251.83 -> return values for this recursive function. So that code is looking pretty good. I think

4259.77 -> at this point, we might be ready to test this one, let's give it a shot here. So some pretty

4264.92 -> tricky codes, not very long. And this is a really core pattern here. Looks like I'm getting

4270.219 -> an error, we have something wrong here. So looks like the answer should have been two,

4274.08 -> but I gave back seven. So I'm counting way too high. So what I'll do to debug This one

4278.849 -> is really just maybe print out my visited. So this is a very common mistake in JavaScript

4286.559 -> want to bring in, I think this example, I could test it manually. What I want to be

4291.97 -> sure to do is maybe at every iteration of, let's say this this for loop, I console dot

4300.199 -> log with visited associate visited changes every time. And I'll run this manually by

4306.97 -> just hitting run. And let's see what we get here. So a few things to note, it looks like

4316.19 -> some of our keys, or some of our items of the set are strings or the zeros a string.

4320.94 -> And other times they're actually numbers, notice that they're missing quotes, that has

4324.96 -> to do with, you know, kind of just JavaScript objects, technically, keys of a JavaScript

4329.249 -> object are going to be always converted as strings, although the data within these arrays

4335.26 -> over here is going to be number. And sets can actually store both types. And so if you

4340.179 -> have like two different types, it's not gonna be able to figure out like that those really

4344.209 -> represent the same node. For example, looking at this visited set over here, I have like

4349.32 -> the number one, as well as the string of one, which is no good. So let's just convert them

4355 -> all to maybe strings. So I'll check visited if it has the string version of my current

4362.01 -> node. So I'll just do the conversion for me. And likewise, I want to add the string version

4367.36 -> of the current node over here. That way, I have very consistent types. So let's run that

4374.429 -> manually, again, should just see all of our strings now. Awesome. And I think we can run

4380.6 -> all the test cases. So that's a really important thing to watch out for in JavaScript. And

4385.429 -> JavaScript is pretty unique in that regard. It just automatically converts all of your

4389.179 -> keys into strings. Awesome. All right, programmers, it's all I got for this connected components

4394.139 -> count problem, what you want to do is really practice this problem. It's actually a very,

4398.749 -> very common interview question. And there are many variations of this problem that we're

4403.17 -> going to do in the future. Hey, programmers, Alvin here, right? Now I want to go over an

4409.159 -> approach we can use for this largest component problem. So in this problem, we're going to

4413.01 -> take in a graph, just like we've been doing as of late. And the first thing you should

4416.429 -> probably do is think of this graph as a picture. So hopefully, you drew it out. So you can

4420.15 -> really understand what this is asking. Our graph information is already given as an adjacency

4424.429 -> list. So it's pretty easy to draw out. So since I have a graph like this, the first

4429.26 -> thing I should notice is it could contain multiple components, right. So here, I kind

4433.89 -> of see two separate islands, two separate components. And I want to consider the sizes

4438.449 -> of each respective component. So if I look at my first component, spanning the nodes,

4442.849 -> 015, and eight, I know that they have a size of four, they're the four represents the number

4447.909 -> of nodes within that component. So I'm really interested in a number of nodes have a component,

4453.099 -> not necessarily the number of edges. If I look at the other component that spans the

4457.61 -> nodes, two, three, and four, that definitely has a node group of three. And this problem

4463.039 -> really cares about the largest component, so I should just return four, because it's

4467.059 -> the largest component size. So when it comes to what this question is asking, you do have

4472.409 -> some familiar patterns if you've been following these problems in order and of course, I always

4475.989 -> recommend that you do these problems in order. So how can we go about solving this one? Well,

4480.13 -> I know I'm gonna need some sort of iterative code that way I can travel and hop to different

4485.099 -> components or different islands, I can probably do some depth first traversal variation that

4489.659 -> also finds the size of a connected component. So let's step through how this algorithm might

4494.929 -> run. On the side. I'm going to list out my nodes to represent how I'm going to do the

4498.949 -> iterations to be In a traversal at every node as my starting point, so I'm going to start

4502.699 -> at node zero. And since node zero is unvisited right, now, I'm going to begin a brand new

4509.03 -> traversal, starting at node zero. And I'm going to mark my nodes as visited as I go,

4514.3 -> because like usual for our undirected graphs, you want to watch out and prevent any cycles

4519.289 -> that you may get trapped in. And I know that this depth first traversal, is going to explore

4523.599 -> this full region as far as possible. And by the power of recursion, it'll be pretty easy

4528.73 -> to implement some pattern that can count every node as we traverse through it. So I'm going

4534.13 -> to treat each of these nodes as just being a single note, of course. And eventually,

4538.36 -> those ones are going to return to my top level call, in which case, I can add them all up,

4542.829 -> getting me a grand total of four. If this feels very hand wavy, and you're wondering,

4547.44 -> like how the heck are we going to code up that pattern, don't worry, it's actually a

4550.76 -> pattern we've seen before. And so I'll cover that in detail in the code. Just know for

4555.209 -> now, it's actually not a big deal to get the count of nodes, right. So now that I know

4559.9 -> that the size of this component is four, what I should do is I guess store it as my current

4564.409 -> largest island or component I've seen so far, because it's the first component that I've

4570.34 -> considered. At this point, I should fall back to my intuitive code. So I look at the node

4573.889 -> of one, what I should notice is this node one is already checked off, it's already visited.

4579.749 -> So there's no reason to start another traversal from this node, because if it's visited, that

4584.739 -> means I have already explored the component that node one is a member of, so I can basically

4590.159 -> skip it, go on to node two in my iteration, since node two is unvisited, I should begin

4594.82 -> a new traversal. Over here, I know that this depth first traversal is going to explore

4599.249 -> that component as far as possible, it's going to go ahead and count all of those nodes as

4603.59 -> one. And eventually some of those counts together, giving me a count of three. And so this next

4609.099 -> component has a size of three, I need to compare that three against my current largest four,

4614.349 -> obviously, the four is bigger, so the four gets to stay as the largest. When I fall back

4619.5 -> to my iterative code, I get to my note of three threes already visited, so no reason

4624.429 -> to start anew. traversal, four is already visited, so nothing to do, five is visited.

4629.409 -> And of course, eight is visited as well. At this point, we're done looking at every single

4633.699 -> node within our graph, and we must have explored every single component, so we can just return

4638.92 -> the final value that we have stored in that largest variable. Awesome. When it comes to

4644.3 -> the complexity of this algorithm, it's pretty straightforward. It's basically exactly all

4648.849 -> of the algorithms we've seen so far, we see that n is the number of nodes and e is a number

4652.969 -> of edges, we know that the time complexity is going to be roughly o of the number of

4657.749 -> edges really just exploring through the entire graph, we can also see that the space complexity

4663.55 -> is also going to be linear, really just O of n. Because through all of this, we're probably

4667.729 -> going to be storing all of our nodes in a set right to track visited. And depending

4671.869 -> on how you implement your traversal algorithm, whether you use depth first or breadth first,

4676.17 -> you're also going to use a linear amount of space through your stack or your queue. So

4681.05 -> overall, we're looking at a very efficient, linear solution. And so with that, I think

4685.729 -> I'm ready to code this one up. What I want you to do though, first is possibly give this

4689.349 -> one a shot on your own first cluster, really just utilizing some code that we've seen in

4693.56 -> the past. So give it a go on your own. If you get stuck, you can find me in the walkthrough

4697.25 -> video. I'll see you there. Hey, programmers, Alvin here, right now let's go over a JavaScript

4703.619 -> solution for this largest component problem. So this problem is going to be really just

4707.789 -> a spin off of our last problem. So we'll hop right into it. And as always, make sure you

4712.139 -> watch the approach video first. And we'll start by building our code that will help

4716.989 -> us start a traversal on disconnected islands here, right? This is connected components,

4721.929 -> we should say. And so I'll start my iterating through every node of the graph, that means

4727.67 -> I just iterate through the keys of my input object here. Because remember, we're given

4732.469 -> this graph as already an adjacency list. So I can say for let node in the graph. So I'll

4739.31 -> give me the nodes like 015, and so on. And what I'll do is I'm going to start a traversal

4747.039 -> here, right? So we're going to pretend I had a function, I'll call it explore size. And

4751.909 -> if I give it the graph information, as well as the node that I want to traverse through,

4756.749 -> hopefully, it actually does a traversal through that entire connected component, right. And

4762.25 -> what I'm going to assume is, let me assume that this function actually returns the size

4768.11 -> of that entire component. So that would be a number right, representing the number of

4772.039 -> nodes in that component. And so if I have that should receive it here, call it size.

4778.17 -> And I know I need some like max value logic for this entire for loop. So I'm going to

4783.139 -> create longest, initialize it to zero. And then from there, I can check. All right, if

4788.42 -> the size of the component I just found, if it's bigger than the longest, then I can replace

4794.53 -> the longest simply longest equals size, that after the for loop, I would just read Turn

4801.179 -> the longest course I need to write this explore size function. So I'll implement this as a

4808.03 -> type of depth first. So I'm going to make it recursive, as for size, taking the graph,

4812.929 -> as well as our current node. And a few things I should watch out for here, they tell us

4820.469 -> that we have an undirected graph. And so we need to make sure that we avoid any cycles.

4826.21 -> So we're also set up here is some classic structure, I'm going to use a visited set,

4831.929 -> we're going to use a set because it gives me O of one lookup and o of one insertion.

4836.86 -> So now that I have my visited set, I can pass it along, as I start the traversals. And now

4842.88 -> let's work on a base case, as well do to get going is check if I visited this node already.

4849.099 -> So if the visited set already has this current node that I need to return, basically avoid

4855.13 -> a recursive call. But I also want a consistent type here, right, so I'm assuming that this

4859.56 -> function gives back a number representing the size at some point in my traversal. If

4863.65 -> I get to a node that has already been visited, that means I counted it already. And so I'll

4868.15 -> treat it as zero right now, because I don't want to double count my nodes, right otherwise

4872.559 -> would be inaccurate here. And now beyond that, what I can do is maybe create a variable here,

4877.539 -> I'll call it size, I'm going to set that equal to one to represent the current node I'm on

4883.119 -> right now, right? If this condition is not true, then it's the first time I'm seeing

4886.929 -> this node, so I need to count it. And we'll also be sure to do is add it to visited that

4893.059 -> way I don't get into a cycle into the node later on. Nice. And at this point, I need

4899.479 -> to make my recursive call on the neighbors of this node. So like we usually do could

4902.86 -> say for let neighbor of graph of node. So remember your shape of data here. So if node

4910.489 -> was a key, like five, when I say, Neighbor of graph node, that would iterate through

4917.679 -> the neighbors a five, zero, and then eight, and so on. And so here, I make my recursive

4923.26 -> calls, I'm gonna call the same function explore sighs, pass along the same graph. But now

4928.15 -> you're situated at your neighbor, and you can provide the same visited set. And here's

4932.42 -> where I do my recursive leap of faith, right, I'm going to assume that this explore size

4936.699 -> function is working. So if it was working, what would it give back, it would give me

4939.619 -> back a number representing the size of that graph, right beginning at my neighbor. So

4946.09 -> whatever number I get back here, I just want to increment my size by that, right. And that

4952.179 -> would accumulate a basically a count of all of the nodes in this fully connected component.

4957.23 -> And after I'm done exploring my neighbors, I would have explored the entire component

4961.96 -> fully. So I can just return my final answer, which would just be the size over here, really

4967.89 -> important thing you need to do is make sure if you follow this kind of strategy, you start

4972.24 -> your size equal to one, and you add to it over time, because this one represents the

4976.789 -> current node that I'm at, I know that every call is going to count its own node. So over

4982.25 -> time, this will actually accumulate everything I need. So feels pretty good, have our nice

4987.32 -> visited logic. And we already wrote our main function here. Notice how we're splitting

4992.289 -> up this code in a nice little helper function here, I think it's the best way to express

4996.729 -> this, it's very similar to some previous problems that we've done. Right, I think at this point,

5002.42 -> let's go ahead and give this a shot. See, what we get, should be able to put it through

5006.38 -> a few different test cases. Nice. And there, we have the largest component to problem.

5012.07 -> So a few things, I want to draw your eye to remember that for your graph problems, or

5015.15 -> you have disconnected components, you're going to need not only your traversal code, but

5020.381 -> some just iterative mechanism, usually just a loop to make sure you can hop to different

5025.639 -> components, right? Because if you only had your regular like traversal function, by definition,

5031.82 -> there is no edge between separate components. So you would never be able to explore the

5036.63 -> full graph. Otherwise, alright, programmers practices, and I'll catch you in the next

5040.46 -> one. Hey, programmers, Alvin here, right. Now let's go over an approach we can use for

5044.639 -> the shortest path problem. So here we have another graph problem, and your graph is going

5048.55 -> to be given as an edge list. So the first thing we should probably do is, of course,

5052.51 -> visualize this graph. And in the context of your code, it probably would be best if you

5055.92 -> convert it into an adjacency list. Since we've seen that pattern a few times in some recent

5060.829 -> problems. I'll leave that part to you. But we're going to end up with a graph that looks

5064.699 -> like this. And in this problem, we're also going to be given a two nodes here, let's

5069.219 -> say W and z, what I want to do is return the smallest path between these two nodes. And

5076.929 -> here I have two obvious paths, right? One way I can get from W to z would be to go through

5081.179 -> x and y. And there I can see that that path length would be three. Do note here that we're

5086.369 -> going to consider the path link as the number of edges within the path. So not the number

5091.11 -> of nodes, right? So that means how do I calculate three here? What's really just three lines,

5096.199 -> right, three edges. That's one way to get from WC another obvious way to get from W

5101.119 -> to z would be to go through VI, which case, I would only need to use two edges. So that

5106.271 -> path line is of course two. And this problem, what I want to do is return the smallest possible

5111.52 -> path length. So I should return the final answer of two here. So we know that this problem

5116.17 -> is going to require us to do a graph pathfinding algorithm. The question is, which one should

5120.139 -> we take, we either can choose, of course, a depth first traversal, or a breadth first

5124.53 -> traversal, I'll cut to the chase here. And both of them would actually give you a strategy

5128.889 -> that works, meaning you can solve this with either a depth first or a breadth first strategy.

5133.499 -> But maybe one of these algorithms would be better than the other. So let's consider the

5137.949 -> possibilities. So let's say I had some large graph, well think abstractly right now. So

5142.54 -> kind of just looking at an abstract example. And let's say I was stepping through some

5146.32 -> depth first traversal. Let me say I have my starting node in yellow, and I'll have my

5151.07 -> target node in blue. So what I want to do is, again, figure out what's the minimum path

5156.36 -> distance between these two nodes, obviously, you know, just in the long run, you should

5161.249 -> get an answer like two here, right, because two is definitely the shortest path between

5165.269 -> these two nodes. If we did a depth first traversal, I know that depth first would force me to

5170.439 -> look in one direction as far as possible, until I have to switch directions, right.

5175.48 -> So for my starting on yellow, let's say we move to the right, that'd be one edge and

5178.769 -> move to the right again, two edges move to the right, again, three edges. At this point,

5182.37 -> I can't move right anymore. So let's say you move downward, so at 456 have to switch directions,

5188.209 -> again, seven, eight. And at this point, we kind of already see that this is going to

5192.019 -> end up possibly getting to the blue target node. But that wouldn't be the shortest path.

5198.34 -> Something unfortunate here is although my star and nodes are really close together,

5201.92 -> a depth first traversal could be unlucky in that it may search in a totally wrong direction,

5206.67 -> and snake all the way through the graph until it eventually finds my target node, at which

5211.239 -> point I definitely don't have the shortest path. So I think a breadth first traversal

5216.579 -> is going to be more useful here. So let's say start at my green node, still my same

5220.539 -> starting point. And if I did a breadth first traversal, I know that breadth first means

5224.749 -> I'm going to explore all the directions very evenly. So it would look like this. So I would

5231.862 -> explore all nodes one edge away from my starting point. And then from there, I would begin

5238.179 -> to explore all nodes two edges away from my starting point. And at some point, I'm going

5243.57 -> to hit my target node. And if it's the first time I'm seeing my target node, then by definition,

5249.039 -> I must have just found the shortest path, right, the shortest path would just be two.

5254.23 -> So that's my high level argument for why a breadth first search is going to be more useful,

5258.21 -> in my opinion, for this problem, let's step through this process a little more algorithmically.

5263.679 -> So let's say I had my original graph. And if I'm gonna do a breadth first traversal,

5268.309 -> I know that I have to use a queue right no matter what a queue is what gives you that

5272.239 -> breadth first order. And what I'll do is eyes the items of my queue, I'm going to store

5277.34 -> not only the nodes, but also the distance from my starting point, that means I'm going

5281.9 -> to initialize my starting note on the queue along with the distance of zero. And that

5287.019 -> represents the fact that all right, that note of W is zero edges away from the starting

5291.409 -> point, because it itself is the starting point. So at any point in time, the items of my queue

5297.01 -> are always going to be pairs, right of node comma distance. So now we're going to begin

5301.92 -> our general algorithm, I'm going to keep iterating. While my queue is not empty, a single iteration

5306.969 -> of breathless would remove the front end of my queue, and I'll label it as my current

5311.86 -> node. At this point, I should check Alright, is my current node of W, the thing I'm looking

5316.59 -> for? It's not, so I need to explore W's neighbors. So I can look at the x node. And I know I

5322.011 -> need to add it into my queue. But when I add it into my queue, I want to make sure I tag

5326.989 -> it with a distance. So if my current node has this zero, I know that a neighbor of this

5332.869 -> node would have distance one, so I just increment the current distance by one. So onto my queue,

5338.449 -> I put an item that says x comma one. And I have a similar scenario for this V node. It's

5343.619 -> also a neighbor of W. And so I put v comma one on my queue as well. At this point, I

5349.9 -> can go to my next iteration, or move the front of my queue. So I look at the x. And then

5354.699 -> I look at X's neighbors do bear in mind that because I have an undirected graph here, x

5359.77 -> really has two neighbors, right, it has w as a neighbor, as well as y. So something

5364.309 -> you should already know is I need to track visited. In other words, when x is going to

5369.08 -> consider its neighbors, it should really only care about the Y, right, I don't want X to

5374.269 -> put w back on the queue, because then I would get an infinite cycle. So I'm just gonna look

5379 -> at the Y over here. I'm going to add it to my queue. Because I know my current note of

5383.739 -> X has a distance of one y must have a distance of two always just incrementing the distance

5389.249 -> by one. Cool. And then I carry on with this algorithm. I removed the front of my queue

5394.59 -> now, which would be the V note. And at this point, I can consider V's neighbors, and I

5399.849 -> do See that one of its neighbors is actually the Xena, that's the only unvisited neighbor,

5404.369 -> I'm going to be sure to add z into my queue and tag it with a distance of two, right,

5409.3 -> because if my v has distance one, its neighbor would have a distance of one grader. At this

5415.05 -> point, you can already see how this algorithm is going to work out. Eventually, this z nodes

5419.67 -> going to leave the queue, and that would actually be my target node. So since I've added a node

5425.17 -> into the queue that matches my target, I know I have my final answer. The two here does

5429.969 -> represent the number of edges we took in that logical path. And I would, of course, just

5435.59 -> return that too. So for the most part, this algorithm just sounds like a classic breadth

5440.499 -> first traversal. Using a queue on a graph, the only interesting bit is now we're also

5444.719 -> going to track the current distance. You know, when it comes to counting the length of a

5448.84 -> path, you need some counting mechanism. And so if you begin your queue with your starting

5453.729 -> node with a distance of zero, every time something leaves a cube, and adds its neighbors, it

5458.381 -> should increment that distance by one. And like you already guessed, this algorithm is

5462.53 -> pretty efficient, because we don't have to traverse through the graph more than one.

5466.28 -> So we'll see that this has a linear complexity. Alright, I think I have everything I need

5470.699 -> to code up this one, I'm sure you're wondering about these implementation details. So what

5474.659 -> you want to do is possibly give this implementation a shot on your own. And if you need some help,

5479.119 -> you can find me in those walkthrough videos. See you there. Hey, programmers, Alan here,

5484.639 -> right. Now let's go over a JavaScript solution for the shortest path problem. So we'll jump

5489.28 -> right in, hopefully, you watch the approach video. And so we'll start by converting our

5493.139 -> edge list input into something more useful for our traversal like an adjacency list,

5497.489 -> we're going to write a very classic function. When I call it build graph, like you expect

5502.42 -> it takes in the edges. And I want it to return an adjacency list. For me, that means a JavaScript

5507.86 -> object, I'll call it graph, by the end of this function, this will help I'm going to

5512.57 -> return the graph and some common code, I'm going to iterate through every pair, right,

5518.789 -> basically every edge, I'll say, for left edge of edges. As I'm iterating, through every

5524.219 -> edge, when I want to do is unpack that edge into its component nodes, I'll call it a and

5532.01 -> b. And now I can start formatting my adjacency list. So I know I want the keys of this graph

5539.699 -> to be obviously the nodes, I want the values to be an array of the neighbors of that node.

5546.25 -> So what I'll do is, it's the first time encountering a node, I'll check. Alright, if this a node

5552.639 -> if it's not in the graph yet as a key, then I should create it for the first time. So

5559.41 -> use it as a key and initialize its value to an empty array, basically, at the start is

5564.579 -> going to have no neighbors. Likewise for B. And then, at this point, I know that A and

5571.739 -> B now definitely exist as keys within the graph. And so I just want to add those neighbors.

5577.439 -> So if I have an edge, like w comma x, I know x is a neighbor of w, and w is a neighbor

5582.849 -> of x. So simply put in say, graph a dot push B, and then just the inverse of that should

5591.369 -> be good to go. Cool. So that should give us our graph. Let's go ahead and use that in

5596.56 -> our main function now. So we'll just say graph equals build graph on the edges. And what

5602.849 -> we want to do now is actually work in our breadth first logic, like we said from the

5606.869 -> approach video. So a few things I'm going to do, I'm going to definitely set up my queue,

5612.229 -> we said that the key to victory here was to not only store the node in your queue, but

5617.791 -> for every like frame inside of your queue also store its distance from node A. So I'll

5623.459 -> just use like a pair of things. So the elements of my queue are going to be always a pair.

5628.059 -> And I'll throw on the initial node A, and also the number zero, because at the start,

5633.249 -> right, this node A is zero edges away from itself. So that's good to go. And over time,

5638.929 -> I'm going to be incrementing. This number, it seems nice. And so let's keep on keepin

5645.249 -> on here. All right, a while loop, classic condition would be all right, while your queue

5650.139 -> is not empty, then I shall remove something from the queue. So always remove from the

5657.619 -> front if you want to follow a true breadth first order. So I can do do dot shift. And

5662.869 -> that will give me back an array or give me back one of these sub arrays here. I know

5667.61 -> it's always going to be a pair so I can just unpack. And I'll just say alright, grab the

5672.409 -> current node as well as the distance. Nice. I'm going to check the node here that I just

5678.469 -> removed from the queue. If that node is node B, that I must have just found a path and

5685.249 -> I know the distance in that path, I can just return it. But if this condition is not true,

5690.709 -> then I need to keep searching through my graph. Since that means I need to add this nodes

5696.13 -> neighbors to the back of the queue. So I'm going to iterate remember that we have adjacency

5700.63 -> lists the entire time. So I'm going to say, for, let's say, Neighbor of graph of node.

5708.539 -> So get all the neighbors of this node. And what I'll do is just add those neighbors into

5715.13 -> my queue. So q dot push, neighbor, try to remember what the form of our graph is over

5721.889 -> here. Maybe as a quick little spot check, make sure on the same page, let me just console

5727.639 -> dot log, the adjacency lists, let's say we took this example manually, just paste it

5733.829 -> down below. And I'll just give it nice little manual runs, I'm not running the test cases

5739.869 -> quite yet. So we converted this edge list into this adjacency list, right. And when

5748.06 -> we say no to something like W, when we say graph, square bracket, no, that would give

5753.32 -> us this array, co authored sorters, iterating, through all the neighbors of this node and

5759.17 -> adding them to the queue, one thing we should watch out for is when we push things back

5763.949 -> onto the queue, we want to maintain the same format. So I actually still want to maintain

5769.11 -> pairs. So I'll make the first element of the pair, the neighboring node on the second element

5774.11 -> needs to be the distance. And since it's a neighbor, its distance would be plus one over

5780.719 -> here. So that's how I'm growing and counting the distance. So let's give this a test run.

5787.059 -> There are a few things we need to work on still, though. But we'll pass a few of these

5790.689 -> examples, at least until we timeout on a particular example. One thing this code is missing is

5796.949 -> any cycle prevention, right? I know that it's going to be a very common scenario, because

5802.4 -> I have an undirected graph, right. And so what I'll be sure to do is maintain a visited

5807.519 -> set, sort of pattern that you're used to, we're just gonna implemented for our iterative,

5811.559 -> breathless right now. So start out with a set. And when you do this iteratively, the

5817.84 -> move would be to make sure that if something is added to the queue, it should also be marked

5823.82 -> as visited. So if I initialize my queue with node A, then I also want to initialize my

5829.409 -> visited set with node A, just like so. So if you're unfamiliar with the set constructor

5836.479 -> in JavaScript, if you want to initialize it with some values, you actually have to pass

5840.499 -> in an array containing those values. So the values of my visited set are just going to

5844.889 -> be the nodes write the node IDs. Cool. And then I want to work that logic into my while

5852.039 -> loop. And so whenever I'm about to add something into the queue, that is, I'm going to add

5858.739 -> a neighbor into the queue, first check if that neighbor is not visited yet, so only

5863.28 -> if not visited has neighbor. Right, so only if this neighbor has not yet been visited,

5872.329 -> then I should add it to my queue. And if I'm about to add it to the queue, like we just

5876.479 -> said anything that interest, the queue should immediately be marked as visited. So here

5881.09 -> I'll say visited, add, the neighbor net should avoid adding any particular node more than

5886.619 -> once into the queue, avoiding any cycles. Awesome. So that feels pretty good. Let's

5893.309 -> give that a test run. Now. We hope to not timeout at least, all that same example, we're

5901.199 -> actually returning undefined where we expect negative one. So if you look at the actual

5906.059 -> prompt, they tell us that, alright, if you can't find a path between A and B, then you

5910.5 -> should return negative one. Let's look at an example or test 04. And you kind of drew

5916.849 -> it out, you would see that there would be no such path that connects B to G. The reason

5921.36 -> we're returning undefined right now is we're gonna finish our traversal mean, meaning our

5926.26 -> queue is going to empty out. And then we're just going to hit the end of this function.

5930.579 -> And if I don't hit a return line by default in JavaScript, I'm going to get undefined.

5935.13 -> So we know if we finish the while loop, and we never found node B, then we can just return

5941.099 -> negative one, that must mean that there is no such path that connects a to b. So let's

5946.65 -> give this a test run. Now. This should be our final version of our shortest path algorithm.

5951.9 -> Awesome. So be sure to practice this algorithm before you move on. And do make sure that

5956.559 -> you understand the choice of breadth first here over depth first, for most of your basic

5961.84 -> just graph problems that require you to calculate a shortest path path meaning just the number

5967.08 -> of edges. Typically, you'll find breadth first easiest way to calculate that hey programmers,

5973.04 -> Alvin here, right now let's go over to the approach for this island count problem. So

5978.119 -> in this problem, we're going to be given a 2d array representing a grid of land and waters

5982.8 -> here we have l characters representing land, and W characters representing water. Let's

5987.78 -> try to visualize this. In this problem we want to do is return a number representing

5992.86 -> the number of islands on the grid. We're going to consider an island as a vertical or horizontal

5998.16 -> connected region of land. So in this particular example, we should return four. Because there

6003.25 -> are four different islands, we can label them as such, this is going to be any type of problems

6007.849 -> for us. And we should really think about it as if we have a graph, I'm going to refer

6011.369 -> to these style problems as a grid graph. And so although we're not given any explicit like

6016.03 -> nodes and edges, I can still think about positions of this graph as nodes. So for example, let's

6022.019 -> consider the indices here. So I have my row indices along the left hand side, and my column

6026.829 -> indices along the top. And I can designate any position of this grid using a pair of

6032.719 -> row and column. So for example, if I looked at position three comma four, that would be

6037.459 -> this position over here. And what I should do is mentally think about a position as if

6042.739 -> it's a node. And if I met some node, I do have some potential neighbors. given any position

6049.13 -> of the spread, I have at most four neighbors in the up down left and right directions.

6055.4 -> given any position of the grid, it's really easy to determine what our potential neighbors

6058.919 -> are, it's really just a matter of adding or subtracting one from either the row or the

6063.34 -> column. Let's generalize this formula. So let's say I was at some position, we'll call

6067.82 -> it our see, if I want it to go upward, that would mean you decrement, the row by one,

6072.309 -> keep the column the same. If you went down, that would mean increasing the row by one,

6075.809 -> if you went to the right, that would be increasing the column by one. And if you want to go left,

6079.249 -> then you should just decrease the column by one, do bear in mind that the top left position

6085.179 -> of our grid is going to be 00. And that's why we have this type of arithmetic rule.

6089.67 -> So now that we're starting to frame this grid problem, as if it's a graph, we can use some

6093.23 -> common patterns, I know that this problem is really asked me to count the number of

6097.53 -> connected components or the number of islands on this grid. So I'm going to need some iterative

6102.84 -> code, probably some nested loops to just iterate through every potential Island and start some

6107.599 -> traversal at that island. So when it comes to our iterative code, we just want nested

6111.719 -> loops to iterate through every row column. That means the iterations should look something

6115.229 -> like this, just moving left to right. until we finish around which case we can go to the

6120.579 -> next row. Let's actually iron out the main logic that we need in our algorithm. So let's

6125.76 -> say we start or nested loops from the very beginning, what I do is check my current position,

6130.34 -> what I want to do is check if my current position is land right now it's water, so I can just

6134.869 -> continue. On the next iteration, I do have some land position. And since I'm on a piece

6139.659 -> of land, right now, what I want to do is explore this land region as far as possible, probably

6144.71 -> using some depth first traversal. And do bear in mind, like most of our undirected graph

6149.63 -> problems, we're going to need to be sure to mark things as visited, so we don't get trapped

6152.959 -> in any infinite cycles. So for example, if I started a traversal, at this position, I

6158.039 -> can go downward. But I can also go upward from here. And I can bounce back between the

6161.59 -> two going up and down, giving me an infinite cycle. So we know how to fix this using all

6166.42 -> of our graph mechanics, right, just use a visited set. So if I do a depth first traversal,

6171.199 -> starting at this position, I know I'm going to mark off all of these land pieces as visited.

6177.809 -> And what I also want to do is make sure that I increments accounts, representing the fact

6182.62 -> that I've just explored some new island fully. So right now, my count zero, since I just

6187.769 -> finished exploring something now my count is one. And at this point, I can fall back

6191.88 -> to my iterative code to scan for another island. So I move to the right, it's water. So continue,

6198.139 -> water continue. Now I have another island. And again, I just do some depth first traversal

6202.489 -> through it. And of course I increment my count. This pattern will follow right? Eventually,

6208.729 -> when I hit the new row, I could be at a land position. But I should also make sure that

6214.239 -> this land position is unexplored, right. So since I'm at position one, comma zero, and

6219.959 -> this land has already been explored, I don't need to begin a depth first traversal. And

6224.56 -> I also don't need to begin a traversal here. And this continues, avoiding starting a traversal.

6230.55 -> Wherever I have a visited piece of land, we know eventually, we're going to hit a new

6234.919 -> island like this one, where I have a piece of land that is unvisited. So at that point,

6240.179 -> that's my criteria for starting a new depth first traversal, I explore this region, increment

6246.08 -> my count, and continue business as usual until I hit this final island that is unvisited.

6251.3 -> And so I visit it and increment my count. And by the end of my iterations, I should

6255.619 -> have my final count of four. So that logic is actually pretty straightforward, just a

6260.45 -> variation of our classic connected component, counting logic, except now we're adjusting

6266.249 -> the criteria we use for looking at neighbors, right, our neighbors are actually going to

6270.719 -> just be either above downward to the left or to the right of our current position. We

6276.37 -> talked about the complexity of this algorithm, we should consider the size of the input and

6280.079 -> the fact that it has two dimensions, right? So if I say that R is a number of rows, and

6284.559 -> C is a number of columns, well and the iterative codes pretty straightforward, I know that's

6289.65 -> going to give me r times C iterations. And if I also consider any potential in depth

6295.729 -> first traversal I do starting at some land. In the worst case, I could have one Giant

6300.38 -> Island, which is also going to be our time to see. So the overall complexity, it's just

6305.15 -> going to be our time See, the space complexity for very similar reason is our time see, because

6310.079 -> imagine that we mark all of these positions as visited, that probably means we'd have

6314.209 -> to add them to some set. Right, so we have our time see different positions. And by the

6318.61 -> end, I could add each and every one of them into my set, the space complexity of our time.

6323.439 -> See also includes any traversal related data structures like stacks, or queues, depending

6328.499 -> on how you implement this one. So overall, this is going to be a very efficient solution

6332.46 -> to solve this one, what you should do is probably give it a shot on your own first, if you get

6335.979 -> stuck, you can find me in the walkthrough videos. I'll see you there. Hey, programmers,

6341.669 -> Alvin here, right now, let's go over a JavaScript walkthrough for this island count problem.

6345.669 -> So as always, make sure you watch the approach video first. And we'll jump right in. So we

6350.36 -> know that this is really just a spin off of our kind of graph connected components problems,

6355.76 -> except now we have a grid graph, right? I can still think about like this grid as if

6359.84 -> it's a graph, because if I think about any particular position of this grid, I know I

6364.881 -> have some neighboring positions that I can travel through mainly, my four neighbors Up,

6369.489 -> down, left and right for me, let me start my laying down some iterative code that can

6374.289 -> begin a traversal at every node or every position of this grid. That way, I can start considering

6379.989 -> different islands, right. So I'm going to use just a for loop for this, I'm going to

6384.34 -> iterate through every possible row column combinations every position. So I'll say R

6388.929 -> equals zero, iterate up to the length of the grid, so grid dot length to our plus equals

6395.909 -> one, and do something very similar for my columns nested inside, right? Watch out for

6401.26 -> some details here though, looking at the examples, we can't actually assume that we're always

6406.76 -> get a square shaped grid square meaning like as if the number of rows was the same as the

6411.499 -> number of columns, because sometimes I'll have like an asymmetric grid occasionally,

6416.119 -> right? If I look at this very first one, it looks like the width is going to be five here,

6422.079 -> but the height is six. So separately for the columns, I want to reference the column lines

6428.159 -> over here. So we're gonna say grid, zero length. Nice. And so at this point, I have some row

6434.75 -> composition, I want to begin a traversal, let's say a depth first traversal at that

6439.75 -> position. So here's where I invoke some like helper function, that will make it a little

6443.03 -> bit, I'll call it explore. And what's going to do is, of course, taking the grid information,

6449.079 -> as well as the row column I want to traverse through nice. And at this point, I think we'll

6454.53 -> actually hop to building this this helper function, then we probably need to fill out

6459.38 -> some more logic within our main driver function here. So let's bake this explore helper function.

6469.32 -> So taking the grid and your row column, and something I should also consider is because

6473.449 -> I know that this is really a type of graph problem, right? I want to prevent infinite

6477.73 -> cycles, right? So consider this, let's say I was somewhere in the middle of my traversal,

6482.13 -> let's say I was at this piece of land, I know that this piece of land is going to travel

6486.3 -> through its right neighbor. And it could be the case that this piece of land now travels

6490.409 -> its left neighbor, so I go left and then right and then left and right. Now it gives me an

6494.71 -> infinite loop, right. So whenever you have this notion of like undirected graph or undirected

6500.179 -> connections, then always guard with a visited set. We've seen this pattern before. So maybe

6506.09 -> up top globally, for the entire traversal, I'll create a visited set. So in JavaScript,

6512.119 -> just a new set, you're probably wondering, you know, what am I going to make the members

6517.079 -> of this set? Well, I need to designate positions, right? Think about it as if positions are

6522.11 -> like the nodes in this grid in this graph, right. And so what I'll do is pass along this

6529.86 -> visit set, so I can accept it as an org over here. And when it comes to using your visited

6535.719 -> set, what you want to do is make sure you combine your row and column because together

6540.469 -> they designate your actual position. I think this is actually worth going through specifically

6546.42 -> more of like a language thing in JavaScript, compared to other programming languages. So

6551.539 -> quick aside over here, let me get myself some more room might be a while. Because if you're

6557.8 -> unfamiliar with sets, and you don't kind of know, their nuances, might actually hit you

6564.219 -> in the butt later on. So let's say I had a set so I'll create an offset. So can you set

6571.88 -> and let's say I added I don't know, like an array containing a row column position. So

6576.34 -> I'm gonna say is, alright, maybe I had position, I don't know, one comma three. And I added

6581.619 -> that into my set. So I do s dot add that position. This is actually a common gotcha in JavaScript.

6587.739 -> If you put any like reference types, like an array or like an object into your set,

6593.519 -> it's actually going to check for reference equality when you check for existence later

6597.8 -> on. In other words, now I can't really do console dot log s dot has one three, because

6606.719 -> this array literal is technically a different array in memory. So I wish I could get like

6612.309 -> true back in this scenario, but I'm not going to get a true. So we'll just run that manually

6616.999 -> see what we get. So like, we say, we're gonna get a false here, which is not so good. So

6622.869 -> instead, your Fix would be to actually convert this into some string data. So instead, maybe

6628.289 -> write as if you had one comma three, because strings are primitive types, and I would actually

6633.38 -> be able to store that string. So whenever I say the string literal, this would actually

6638.03 -> give me a match now, so I should get a nice true here. Awesome. So we'll want to use that

6644.639 -> pattern to our advantage. And so maybe I'll start by creating some position variable,

6650.63 -> that's going to be like the string of FIDE a version of our position. So just take my

6654.61 -> row, maybe add a comma, and also put the column here. Nice. And the reason I want to comma

6662.63 -> separate is, I need to have different bounds for my row and column. In other words, imagine

6668.76 -> I had a row of let's say, 12. And I had a column of four. If I turn that into a key,

6677.13 -> or a position, that would give me position as looks like 12, comma for another scenario,

6683.349 -> let's say I had row one, and then column 24, that would give me a position of this right?

6692.329 -> one comma 24. Right, it's really important that you put a comma to separate your row

6696.94 -> and column positions, because imagine, I didn't put the comma, then it would have a collision

6702.36 -> here, I have two totally distinct positions, right? 12, four, and 124. And if I don't put

6707.639 -> a comma, they look like they have the same position key. So that's why I need to comma

6712.399 -> separate them. Common gotcha there. But now that I have this position, I can use it to

6718.13 -> my advantage in this visited set. So if I've already visited this position, so if my visited

6726.059 -> has this position, then I should exit, right, I need to return something. And I want this

6731.38 -> explorer function do something similar, like we've done in our old component problems,

6735.659 -> I want it to return a Boolean indicating whether or not this is a new island that I'm exploring.

6741.07 -> So if it's visited already, that's definitely not new, right. So just return false, meaning

6745.051 -> it's not a new island. If I make it past this if statement, in other words, if position

6749.559 -> is not in visited, that I need to mark it as visited right now, second, do visited,

6754.479 -> add this position. So now I have my core like cycle prevention logic. Beyond that, I have

6761.229 -> a few other scenarios, we know that in our traversal, we're going to look at our different

6765.489 -> like neighbors. And so what I want to do is make sure that I'm in bounds here. So I'm

6769.869 -> going to check, like to split this up into variables, I'll say, one, a boolean variable

6774.57 -> called row in bounds. And I'll do is just check if zero is less than or equal to the

6780.86 -> row. And that row is strictly less than will say, the length of my grid. So I'm just checking

6788.889 -> to see if my opposition is in bounds here, I do a quick check, I need to be inclusive

6795.08 -> with zero because zero is a totally valid index, right? I need to be exclusive with

6800.019 -> the length because imagine I had a grid with length five, it's last valid index is four.

6804.889 -> So I need to be strictly less than here. And I'll write a similar variable for my column

6810.11 -> in bounds, just like this. And at this point, I can write a nice semantic if statement check,

6818.9 -> all right, if your row is not in bounds, or your column is not in bounds, then exit, right?

6826.96 -> So return like before I can return false, right? Because I should not consider like

6831.899 -> an invalid position and a balanced position as an island, right? So that's looking good.

6838.849 -> Final base case I need though is, what if my current position is water, right? I only

6844.059 -> want to do my traversal through land. And so I'll add another statement for that. So

6850.06 -> up here, I can check. All right, if my grid at row column, if it's equal to water, then

6856.719 -> also return false. No reason to count it, it's really important that you put this in

6861.159 -> bounds check before you index into your grid, right? Because imagine that your row and column

6867.48 -> were out of bounds. If you write line 15 like this, immediately, you're going to get an

6872.07 -> out of bounds error. So start with your guard to check if you're in bounds if you want it

6876.889 -> to because most of these conditionals they all return false have the same consequence.

6881.929 -> You can probably or them together. Typically I like to keep them separate. That way I always

6885.809 -> remember to write them typically for like your grid graph problems. This is very canonical

6890.699 -> code. Alright, so if I make it past all of these base cases, and I have the recursive

6895.88 -> case, so I must be at an unvisited piece of land. And when I want to do is do my depth

6901.78 -> first traversal, right. So here's where I explore my neighbors and I have four neighbors.

6907.469 -> If I wanted to go above that I decrement, my row by one, keep the column the same, pass

6912.829 -> along the same visited, because remember, we have like the array indices here. So this

6917.789 -> is row zero, this is row one. So we'll lower row numbers mean upward, in the same way,

6923.869 -> lower column numbers mean to the left. So this is up, this is down by do just minus

6932.349 -> one over here, that would be to the left, then plus one on the column would be to the

6937.399 -> right. Cool, and I can keep this code very flat as it is something that I'm a huge proponent

6944.649 -> of when you write recursion, for the most part, I always try to make sure that I don't

6950.539 -> look before I leap. In other words, just from this logic alone, it couldn't be the case

6955.76 -> that row minus one is out of bounds. But that's okay. Because if it's out of bounds, when

6960.809 -> I evaluate this call, it's going to immediately be caught by this base case, right. And if

6967.179 -> I express my logic like this, if I don't look, before I leave, if I just leap and then catch

6971.169 -> myself with the base case, you don't have to write repetitive code. In other words,

6975.849 -> some people write code like this, where it's like, Alright, if row minus one inbounds kind

6981.34 -> of using pseudocode. Here, they would have to write row plus one inbounds. And you would

6986.28 -> have to write a guarding if statement around every recursive call, instead, just write

6991.28 -> one base case. And you can catch all of these different out of bounds, right. So that's

6997.449 -> why I prefer it this way. And so I know that by the time I return out of these recursive

7004.119 -> calls, I'm back at this segment of my code. And what I can do is return true because I

7010.169 -> must be finished with that traversal. And the reason I'm returning true is true symbolizes

7015.749 -> that I've just finished exploring a brand new island, so I need to count it. Nice. It's

7021.199 -> also consistent with the data type, I have Boolean for this explore function. So for

7026.939 -> the most part, this looks like really just a spin off of our previous like graph, depth

7031.48 -> first code. And now I want to use that boolean data in my main function here. So here's where

7036.949 -> I can actually count my islands. So guess I really need some logic here that says initialize

7042.3 -> some counts equal to zero. And whenever you find a new island, increment that count. So

7048.51 -> if I just have found a new island, we're going to get back true from this this call, right?

7053.219 -> Because remember that I'm beginning a traversal, starting at this row column position. So if

7058.409 -> it gives me back true, then I can totally increment my count by one. Notice that whenever

7065.449 -> I begin a traversal on a position I've seen before, it would have been added to visited

7070.8 -> before. So I would return via this if statement on line 21, I return false. If I return false,

7077.77 -> then I don't double count that island. So I do need a combination of both iterative

7084.949 -> code to potentially leap to different islands. But I can use a visited set to prevent myself

7090.229 -> from double counting any particular Island. So this is looking pretty good. Let's not

7095.8 -> forget to of course, return our counts at the end. Let's give this a run. This will

7103.079 -> probably be the first in a series of these like grid graph problems. Really try to understand

7109.11 -> how we can think about still a grid as if it's a graph, right? We just have different

7113.03 -> rules for how we look at our neighbors. Right? Now, a node is really a position and its neighbors

7118.219 -> are its four neighbors Up, down, left and right. Alright programmers, I want you to

7122.099 -> practice this pattern because we're going to see it in the next few problems. I'll leave

7125.8 -> it to you see in the next one. Hey, programmers outlane here, right now let's go over an approach

7132.459 -> for this minimum Island problem. So we're going to be given here a grid containing a

7137.519 -> water inland really just some characters inside of our grid. So of course, as always, let's

7142.3 -> visualize this. And what I want to do in this problem is return a number representing the

7146.34 -> minimum Island size, we're going to consider an island, a connected region of vertical

7151.69 -> or horizontally connected pieces of land. So for this particular input, our answer should

7157.169 -> be to looking at our grid, I have three separate islands. And they all have different sizes,

7161.439 -> right? sizes, a four, two and five, I just choose the smallest of the islands. So that

7166.399 -> would be the two over here. So how can I actually come up with a strategy for this one, you

7171.36 -> should already know that this is just a spin off of our previous a grid graph problem,

7175.77 -> where instead of doing just a count of the number of islands, now I want to find the

7181.169 -> sizes of islands. I know to actually look at different islands, I'm gonna need some

7186.11 -> nested code, but I'm also gonna need some depth first traversal code to explore a single

7191.209 -> Island. So overall, this should be a pretty classic strategy for us. So let's say we start

7196.489 -> attacking this we know we're going to begin our nested loops in the top left corner And

7201.439 -> if our current position is water, then we actually don't need to do anything. next iteration,

7205.84 -> I have some land. At this point, I could begin on my depth first traversal. And I know that

7210.739 -> I should be marking things as visited to avoid any infinite loops, right. So by the time

7216.219 -> this traversal completes, I'm going to mark all of these guys as visited. But I also wanted

7221.41 -> to determine the size of this entire island region. So every time I get a position that

7226.89 -> is land, I should treat it as one. And then when it comes to how I implement on my traversal,

7232.409 -> I can just gather up these ones, right, just add them all up. So that would look something

7236.71 -> like this. And for my top level call for that traversal, I should get an island size of

7244.389 -> four. And so if that kind of traversal algorithm, especially how we compute the size of the

7249.459 -> island, is pretty hand wavy, don't worry that when we actually go through the code walkthrough,

7253.429 -> it's just a matter of some recursion, and some recursion we've actually seen before

7257.399 -> in past problems of the course. But any case, now that I have this island size of four,

7262.119 -> it's actually the first island that I've seen. And so I'm going to consider it the mid size

7266.349 -> so far. But I need to keep looking in case something is smaller. So move to the right.

7271.01 -> So if it's water, I do nothing, water again, do nothing. Now I have another islands, I

7275.659 -> begin my traversal market these as visited. And when I find the size of this island, of

7280.32 -> course, it's going to give me two, I compare that to to my current mid size two is smaller,

7287.369 -> so I store two as the mid size so far. And we just continue business as usual. Note that

7292.649 -> when we get to a piece of land, we really want to make sure that it's land, but also

7297.349 -> a piece of unvisited land. So right now on that piece of land, but it's visited, so I

7301.8 -> should not wear I don't need to start traversal here. Likewise, for this position. Eventually,

7307.909 -> I'm going to hit some new unvisited land, in which case I should begin my traversal

7312.3 -> at Explorer, this region, and I want to count up all of these pieces of land. And I should

7318.149 -> realize that the final size of this island would be five, I can compare that five against

7324.26 -> my current min, five is bigger, so the size of two gets to stay. And I can just end up

7329.09 -> returning the minimum size by the end of this algorithm, basically representing this island

7333.989 -> of size two, the complexity of this algorithm is straightforward, we should say that the

7338.459 -> size of our input is r times C, because we have our rows and C columns, in which case

7344.489 -> a time complexity is simply our time C, right, we have to iterate through every row column

7349.84 -> within the grid. And even when we begin a traversal, in the worst case, we could have

7355.59 -> an island that spans the entire grid, in which case it would also be our C. Right. So overall,

7362.229 -> our full complexities are time c space complexities are time C as well. And do know that this

7367.719 -> is technically a linear solution in the size of the grid, right because the grid itself

7372.749 -> is exactly r times C positions. So with that, I think we're ready to code this one up and

7378.38 -> try it on your own first. And if you get stuck, I'll catch you in the walkthrough videos.

7382.01 -> See you there. Hey, programmers, Alvin here, right now let's go over a JavaScript walkthrough

7387.76 -> for this minimum Island problem. So we'll jump right in, make sure you watch the approach

7391.929 -> video. As always, this is just a nice spin off of our classic island hopping logic. But

7397.18 -> for a grid graph, right. And so let's start with the iterative code that can help us begin

7402.07 -> a traversal. Starting at every different position of our grids, that just means some nested

7407.309 -> loops. So start by iterating through all of the rows and columns. So r equals zero, go

7412.63 -> up to while r is less than length of the grid, also do our plus equals one and very similar

7420.019 -> loop for my column. But do make sure that you reference your inner column line because

7426.659 -> you could have like a rectangular shaped grid over here. And what I want to do now is begin

7432.679 -> a traversal starting at every row column. So I'm going to assume I have a helper function

7437.739 -> here that does that traversal, I'm going to call it explore size. That's because in the

7442.769 -> long run, I'm interested in the size of that island, right, so like a number representing

7446.5 -> how big or how many positions that island spans. So I'm going to pass along the grid

7451.689 -> information as well as the position. And I know when it comes to all of these like undirected

7457.849 -> graph, traversals should probably guard against your loops. And I have some foresight here.

7462.17 -> So I'm going to pass along a nice visited set, which I can maintain globally for the

7466.149 -> entire traversal because there's only a good reason to explore a position once right. So

7471.719 -> I'll create const visited gonna make it my neighs JavaScript set. And a few reasons for

7476.82 -> that. Well, for one JavaScript set, gives me O of one lookup, but also o of one insertion.

7482.349 -> So it's going to be a really quick data structure to use. And from there, we probably have to

7487.78 -> add some more logic over here to actually do something with the size but for now, I

7491.33 -> think I'm going to switch gears and actually take a look at building this helper function,

7496.53 -> right. So I think the best way to build this traversal is to use is a deaf purse, typically

7501.76 -> just my go to for problem like this, it's going to take in I know the grid, the row

7507.449 -> in the column and also visited, I need some a base case is very classic base cases, I'm

7512.71 -> going to start by checking if this row column position is inbounds. So my favorite pattern

7517.399 -> for that is to split up in some variables just makes it easier to read and debug. So

7521.43 -> I'm going to say is my row inbounds and just make that like a boolean variable. So I'll

7526.719 -> check if, let's say, zero is less than or equal to the row, I need to say and right,

7535.76 -> and that row should be strictly less than the grid length. So this Boolean would only

7543.51 -> be true if it's in bounds, right? And something very similar for my column bounds should be

7550.61 -> between zero and grid zero length. Nice just like this, I believe. And then I can write

7559.8 -> a nice if statement using both clauses. So I can say, all right, if let's say your row

7565.38 -> is not in balance, or your column is not in balance, then you're definitely at a bound.

7572.34 -> So you should probably use some base case here, right? So we're all choose to return

7576.28 -> here is zero, because I want to keep a consistent number, right consistent return type. That

7581.53 -> is, I know that this function has a kind of goal of returning the size of the explored

7586.079 -> islands sizes a number. So even in my base case, I need to make sure I return some type

7589.829 -> of number, returning zero to represent that, hey, if this is out of bounds, it's not going

7593.849 -> to contribute anything into the count of the size, right, which is good to go. I need some

7599.149 -> other base case here. What if my position is inbounds. But what if it's actually water,

7604.459 -> I don't want to count that as well. I only want to count islands. So land right. So quick

7609.369 -> fix, what I'll do is add a new base case, I can check if my grid at row column, if it's

7616.519 -> equal to the water character. So a capital W can also return zero. If you want it to,

7623.639 -> you can also maybe merge these into like a single if statement, just write a bunch of

7627.659 -> ORS, I kind of like them separate because it's just easy for me to remember what each

7632.169 -> of them does write a final conditional have here is alright, if I make it past both of

7637.869 -> these base cases, it might be the case that this position is land, but it's land I've

7643.619 -> already visited. So here's why I work in my visited logic, I'm going to represent a position,

7649.17 -> like we said in the last episode as really just a string. So I can put it as the members

7654.919 -> of my visited set. So I'm going to say position to have to be the row plus a comma plus the

7661.229 -> column. So just representing the position, that's because I can't add like an array into

7667.679 -> a visited set, and then look it up later. And so if visited has the position, then it's

7673.8 -> a duplicate position that I've explored. So return zero. Otherwise, it's not been visited

7679.19 -> yet. So I must be visiting it right now. So I can add it. Nice. So I have my base cases

7684.739 -> laid down. Now I'll need my actual recursive code. So I'll explore my four neighbors. By

7690.16 -> now you should be familiar with this pattern. So go upwards, a row minus one column pass

7694.889 -> on the same visited. So I'm going to explore my up down left right neighbors respectively.

7699.969 -> And I do my recursively buffet theory, right. So what type do I expect back from these calls,

7703.869 -> they're going to give me back a number representing the size of the island that my neighbor is

7708.849 -> a part of. But if my neighbor is part of some larger Island, then I am too because we're

7713.559 -> connected right to our neighbors. And so I want to create the grand total of all of these

7718.369 -> return values. So I'm going to create some size variable, let's say let size, I'm going

7722.949 -> to initialize it to one over here, it's going to be one and not zero, because the one represents

7728.039 -> my current position, my row column. And whatever these calls return, whatever number I'm just

7734.579 -> going to increment my size by that number, like so. Then finally, I can return our total

7740.879 -> size over here. So that will do my depth first traversal, because it's recursive, but we'll

7747.349 -> also tally up the size of this island region. Cool. So now that I have a working explore

7754.439 -> size helper, let's use it in our main function here. So I'm going to get back a number from

7759.929 -> this call. I'll call it my respective size. And what's great about this logic is if I

7767.09 -> have a Island or position I've already seen before, and I encounter it again in this this

7773.59 -> for loop, then I would just return early because I would hit this base case, right? If something

7777.791 -> has already been visited, just automatically return zero, because I've already considered

7781.4 -> it, no reason to consider it again. But now I need my minimization logic, right, I want

7786.28 -> the size of the smallest Island. And they tell us in the problem that we can totally

7789.84 -> assume that your grid contains at least one island. So I think a great default value here

7794.159 -> is to use positive infinity so I can set some will say min size variable To be positive

7800.699 -> infinity, JavaScript, if I make it positive infinity, I know when I encounter any like

7805.919 -> valid Island size, it's going to be less than infinity. And it should replace it. So now

7811.55 -> I can do some min logic here and check. All right, if the size of this island is less

7815.909 -> than the minimum size I have seen so far, then just replace that min size with that

7821.84 -> island. Then after I'm done with all of these traversals potential reversals, I'll return

7827.369 -> my mid size. So some classic patterns here. There's one nuance that we're not considering

7833.71 -> how to run the code, and we can debug it together. So it looks like we failed example. 00. So

7839.69 -> the very first example we expected to answer to, we accidentally gave back zero. If you

7844.999 -> look at that first example, it's pretty obvious that Yeah, the minimum size is two representing

7848.739 -> this island over here. The reason we're giving back zero is according to our code. Let's

7855.439 -> see we're on like the very first iteration, I'm going to respond it, I know that row is

7858.559 -> going to be zero column is going to be zero, that means my position would be this w over

7862.379 -> here. When I make the recursive call, and I pass along position 00, I know that it's

7868.65 -> going to immediately return zero because that position is water. And I'm going to check

7873.36 -> Alright, is that zero, less than infinity it is, so I'm going to replace min size with

7878.11 -> zero. But if I think about it, zero doesn't even represent a real Island. If an island

7883.3 -> has a size of zero, then it's not an island at all, it was a piece of water, right? And

7887.889 -> so I want to add some additional logic here to only actually look at nonzero quantities.

7893.199 -> So only do the comparison if that size is also valid. So size should be greater than

7899.159 -> zero, of course. And we'll want to add these together. So let's try that again. Just a

7907.849 -> little, little detail over there that we need. Awesome. And there we have a solution for

7911.719 -> this minimum Island problem. So we've seen this pattern a few times now, right or classic

7916.53 -> island hopping logic. So when you think about islands are like connected components of a

7920.749 -> graph, this should be your first kind of go to algorithm. Alright programmers. So that

7925.26 -> wraps up our course on graphs. I hope you learned a ton during the course. I definitely

7928.939 -> had a blast making it Be sure to head to Shruti dotnet, where you can continue to practice

7933.11 -> more graph problems, as well as explore any other data structure algorithm topics. I'll

7937.349 -> see you there.

Source: https://www.youtube.com/watch?v=tWVWeAqZ0WU