Graph Search Algorithms in 100 Seconds - And Beyond with JS

Prepare for a technical interview by learning about the graph data structure and basic traversal algorithms like depth-first search (DFS) and breadth-first search (BFS). fireship.io/co...
#compsci #JavaScript #100SecondsOfCode
Install the quiz app 🤓
iOS itunes.apple.c...
Android play.google.co...
Upgrade to Fireship PRO at fireship.io/pro
Use code lORhwXd2 for 25% off your first payment.
My VS Code Theme
Atom One Dark
vscode-icons
Fira Code Font

[@Fireship]

Do you want to see more videos with a technical "interview prep" focus? Usually I cover practical projects, so curious to know what you think...

[@sadn1ck]

YES please! Much love!

[@nicolasferrero9928]

I like this videos more than others

[@PrakashVl]

Yes interview preparation, this one is awesome

[@abhinav.sharma]

YEEEEEEEEEEEEEEESSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS

[@sagnikpradhan3594]

Yes!

[@sagnikpradhan3594]

I would love more algorithms, data structures, and ML too!

[@nils42]

Thanks, with my 6 years+ experience as a Frontend-dev, I now feel like a junior-dev again 😅

[@shygrammer]

you just said it!

[@meco]

I would’ve needed this for my computer science class 😫😫 Once again your content is the high quality learning we all needed

[@athulp6591]

In my case , it is right on time.

[@miteshkumar3183]

This is a basic topic in a first semester computer science class.

[@anirudhtv]

IF CS WAS A MOVIE THEN THIS MAN YOU WOULD BE THE AUTHOR

[@YoloMonstaaa]

Movies have script writers and directors as key creative roles. No authors.

[@calvinebun-amu5397]

100%

[@Fireship]

I'm writing a screenplay titled "CS - The Movie" ;)

[@raymondmichael4987]

Fireship, I'll definitely watch it. Greetings from Tanzania 🇹🇿

[@abelkidanemariam6485]

another Ali gate fan here

[@aykborstelmann8623]

I really appreciate this format especially the combination of 100 seconds & beyond 100 seconds

[@Loopmootin]

3:25 "go slowly and explain every step!" while going on for 10½ minutes like an absolute rap god xD Had to watch the video back to back twice and still only got half of it, but loved all of it ^^

[@ihavetwofaces]

+1 for the "x in 100 seconds... but wait there's more!" format. Getting a brief overview of the concepts followed immediately by a more in-depth implementation of those concepts is a fantastic way to structure the video.

[@sathishshaj7815]

This video is more than worth of my three year CS degree 🔥

[@Pogibakayo]

So glad. While these X in 100 seconds videos are great for some topics, this definitely needed a longer one.

[@Fireship]

Thanks! Yeah, trying to decide if I should make them as completely separate vidoes

[@Pogibakayo]

Fireship I’d certainly love that! But honestly, anything you put out is gold. You’re on fire.

[@Ajay-ku6oq]

@@Fireship Maybe release them simultaneously so that people who want can watch both and there is a higher chance of one going viral.

[@Sunwarul]

@@Fireship Please make this type of video with a slow pace. Your teaching style is good. but just take longer and bit slower-paced videos. Give some time to grasp the concept along. However, like these videos. Thanks!

[@LineageFalcon]

Fireship Yeah, I think u definitively should do that. Some of your viewers want more in-depth information and with a bit more time to consume it. So I think it is a good Idea to do a 100 secs version and a in-depth version. Anyways I really appreciate your work and passion. Thank your for your vids. Have a nice day. :D

[@simplyweird6369]

Definitely want Algorithms, Design Patterns and Data Structures 🙏

[@099watcher]

That was sweet! Please create a playlist of data structures and algorithms. Great content, keep it up 👍🏻. 🔥🔥🔥

[@kinnikuchu]

You go way too fast, yet you give an introduction as for newbies.

[@Brunoenribeiro]

fireship does youtube like no other channel the "basics in 100s + deep dive" format is a blast, man

[@MarsTheProgrammer]

For anyone that didn't see how you get the steps at 9:49 it's `DFS found Bangkok ${visited.size} in steps`. Use the visited size.

[@golddropper2747]

Very clear instructions. I only know Python and I completely understood your coding process with Javascript.

[@darshangowda309]

Wow! This is awesome 🙌 would love to see more of this!

[@TheGitGuild]

This is really nice. Also try making the speed 2x and watch it like 3 times if you want to overclock your brain. But it could cost you a few more seconds tho :/

[@oladimejiakande9070]

😂

[@TheNewton]

5:32 Javascript destructuring in 100 seconds

[@eshaan7_]

more like JavaScript de-structuring in 100 milliseconds.

[@AiguretDuren]

I really enjoyed working with these data structures and algorithms in JavaScript. I would love to see more of this!

[@RTshots]

I didn't know I needed a fireship video about cs theory until I watched one. Plz do more

[@lucasoliveira-xs5yh]

Your channel is sooooooo awesome, congratulations! One question that I have: Is the set used at the DFS function a memoization technique?

[@magne6049]

0:26 The notation you used actually indicates it is a bi-directional graph, meaning directions in both ways. An undirected graph would have no arrowheads (since arrows indicate direction), but simply a line.

[@magne6049]

@Fireship

[@suryasarkar9681]

More on graphs please. This was one of the best explanations of graph traversal on the internet ❤

[@Zeda_]

This video is awesome! I love seeing these 100 second videos pop up in my feed, they’re always fantastic. One note though: an adjacency matrix does have very bad space complexity, but part of the reason for that is that it’s making the trade-off for time. It actually is quite time efficient to check specific connections [O(1)], so it just depends on what your program is prioritizing or needs.

[@kritikkaushal6305]

straight up one of the best channels on yt

[@ikezedev]

It is so nice knowing that you decided to use recursion instead of stack in DFS to show to show it can be down either way. Thanks a lot Jeff 😍

[@marshallmurray8050]

Yes, I would definitely like more videos with technical interview prep focus. I'm probably a ways off of an actual interview, but it's nice to mentally prepare proactively because I'm such a good procrastinator!

[@trompowsky12]

*Music in **0:00**?*

[@emsourcemedia9178]

This is by far the best explanation of node.

[@akam9919]

Got an interview in 5 min. Thx!

[@teddified3845]

This hooked me like crazy. Please do more data science and algorithm videos like this. Loved it!

[@daheck81]

100 seconds of different time complexities as in the Big-O-Notation would be awesome. I tend to forget how they work when I haven’t dealt with them in a while (same with Regex) so I think a 100 second reminder would be perfect!

[@youssefmuhamad3213]

That was awesome, keep it up with more advanced stuff

[@kevnar]

I had to figure all this stuff out on my own when trying to implement A* pathfinding in a game I made. The tutorial I followed used an adjacency matrix. But my game maps were 1000 x 1000. The whole thing crashed when it tried to build the matrix. So I manually went through and converted the graph to a list structure, so only nodes with edges were stored. I guess I could have saved the whole thing to the hard disc instead of keeping the whole graph in memory at run-time, but I learned a lot fixing that problem.

[@tygobolink5743]

It feels so bad that you upload this video right now. It's a great video and in explains the problems clear. But for a school assignment I had to Depth First Search a specific list of nodes and links. I did need a couple of hours to figure out how to this works. I nailed it but not as clean as you explained the problem and the solution. Thanks for the great video's you make!

[@geo9115]

I wish it didn't take my data structures professor 3 weeks to explain this concept. Thanks for the 100 second rundown!

[@Aaronmoreno]

one of my favorite videos so far!

[@bmejia220]

Wow brilliant tutorial man brilliant lesson thanks so much learning so much here

[@jasonlantz3808]

linear time based on edges... linear space based on nodes... O(n), O(m), respectively...

[@optimusdebugger9638]

yes please we want to see more videos like this!

[@Jaybearno]

Graph theory… the only class I almost straight flunked in college and still shiver thinking about. Maybe it’s easier now with code, but in theory it’s confusing AF

[@ttul007]

great video! quick and efficient refresher for stuff i touched 10+ years ago when i did my bachelor's. thanks :)

[@joshwasuresh6445]

He just solved the most difficult problem in the world 😳...

[@Melvin420x12]

This is awesome. Thank you. I love the “beyond the 100 seconds”. Never heard of the Map or Set object. These kind if things make me so excited. Do you make these videos on your own or is there a team behind Fireship?

[@tartarus1322]

Maps are some of the most beautiful data structures that you’ll ever see. A Map is a hashed data structure, which is some of the most useful shit you’ll ever use. A HashSet (not implemented in JS) is incredibly useful. They’re so useful because of their ability to retrieve a value in O(1) by value. This can find if an element exists in (ideally) O(1) rather than logn which is a binary search.

[@Melvin420x12]

Tartarus13 Sounds interesting! Do you have a source where we can learn more about this?

[@theshermantanker7043]

@@tartarus1322 well, that is until you start getting hash collisions, that's when maps start rearing their ugly head

[@coolj7086]

Really nice video! Although using map and set do add a O(logV) factor in the final complexity and, depending on how js handles popping elements from the front of the array, an O(V) factor

[@hamidbakhtiari3986]

i would really like to watch more videos like this

[@dnk1312]

Every time the outro music fades in, I can literally feel that 'i get it now' rush ! Thanks a lot and keep up the outstanding work !!

[@danbergelt8969]

Great video. You should totally do a whole series of fundamental CS concepts.

[@coordinates_]

Can you vlog how you make this quality videos?

[@stith_pragya]

Thank You So Much for this wonderful video...🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@nero-kun-here]

Very good quality content! I love it! need more videos like this....

[@austinealagi]

Thanks you so much for this video ❤️ you are a life saver. I will need more of this video.

[@luis96xd]

Whoa, amazing video! 😄 I also liked the "Beyond the 100 seconds" I learned a lot of objects and its functions How we could create a recommendation algorithm using graphs in Javascript? What variables or objects we need to implement? 🤔

[@gagahkharismanuary9385]

Sooo cool dudee!! I really take my notes and learnt from your explained

[@aleaallee]

I'm lucky here in europe most companies interview you about the technologies you are going to use to develop websites/web apps and not algorythms.

[@kuchbhi6455]

Jeff please, we need a DSA course. I feel I'm wasting a lot of time learning DSA topics with other resources. Can you please spend sometime on creating a DSA course. - Nobody ( who loves your work a lot.)

[@ritambanerjee3668]

TBH BFS actually guarantees a solution (if it exists) and gives you the shortest path (if implemented correctly), so I guess to check if a path exists both BFS and DFS can work but if you want to find the shortest path use BFS.

[@CodeMonkeyG2011]

The format of these videos is brilliant! 100 seconds intro and then, if you want it, some practical implementation.

[@deepaligarg7643]

Very good video. What will be the space complexity for each?

[@MCMadk]

Amazing content. Thanks !

[@PraveenKumar-ft2kr]

Amazing one.. WE need more of these :) Bring it on brother ✌

[@PsHarneja]

Every other channel: Increase the video speed to 1.25. This channel: Decrease the speed to 0.75

[@MASTERISHABH]

Nice! Just one question how DFS was more efficient than BFS for checking route existence? What if Bangkok was the second neighbour in the first node itself? In BFS, it could have been found in 1 go but DFS would first traverse all the nodes from the first neighbour to come back to the second one. This will be true for vice-versa. Also, how to determine when to use DFS and BFS respectively? Suggestions? 🤔🤔

[@vectrangle]

Jeff is wrong when he says DFS is more efficient than BFS here, it happened to be that way in his example but only due to luck. You would usually use BFS for any pathfinding problem because it will find the shortest solution first. In my experience DFS is rarely more efficient but it is often easier to code

[@beinyourguard]

I sincerely don't think I'll ever be a good developer as you are.

[@rauchu5861]

what is an API,rest api etc. in 100 secs please in the most clear way.

[@sqarcle]

For faster solution to the airport problem you can use dp and in each node store their children.

[@kimimhd123]

please, more videos like this

[@AdrenalineAkash13]

Greatest explanations i've ever seen on KZbin hats off @fireship

[@s.hariharan6958]

you are Saviour of cs students 🙇‍♂🙇‍♂...

[@nomtijorti]

great content as always!

[@davidvideauortega287]

Hellllll I loved this video. THANK YOU!!! This channel is seriously awesome. One of the best coding channels in the entire internet. ❤

[@kristofs8893]

You just saved me a ton of time. Thanks for the video. :) Keep it up.

[@Endede]

For your BFS implementation, I think worst case time complexity ends up as O(E + V^2), because the shift() method is (probably) O(N) for N == length of the array. To achieve O(E +V) A "real" queue implementation is needed, that implements enqueue()/dequeue() in constant time.

[@shiblynoman310]

Please keep making more algorithm related videos. :)

[@napoleaonbonaparte6005]

You forgot to initialize the visited Set with "PHX", since it's the first node of the QUEUE which means it's already visited. Nice video tho.

[@hendrickmanenga9213]

Some people were really born to teach.Congrats

[@nulI_dev]

this makes so much more sense than any CS video i've ever watched

[@quantumcaffeine]

Great video, but I'm a bit confused by the DFS example. As written, it looks like it will continue searching after the destination has been found as long as one of the parent nodes has unvisited children. How do you ensure that the algorithm stops immediately after the destination has been found?

[@nomiscph]

In the DFS - i would normally pass start as an array and then pass all destinations to a parent array if they do they have not been part of the visited set and then do that then instead of looping back and forth over a tree your taking a whole layer of “children” every time - if that makes sense?

[@tinmank]

Hello, are you planning to continue with this topic? I was wondering how the same algorithm would be with the weight to paths. (instead of the shortest, cheapest path) I know there are other sources explaining but none of them explaining as you do :)

[@arjunyonzan8557]

thank you, will be practising a lot

[@akifimran9780]

Yes more please

[@VigneshDhakshinamoorthy]

Is it fair to say @1:25 accurately describes all of us right now? Great video by the way, cheers! Keep it coming. DONT STOP! PLS!

[@MatteoGauthier]

Very interesting, I want more vide like this !! 🔥🔥

[@tijanisylla1348]

TypeError: Cannot read property 'push' of undefined

[@abhinandankumar4584]

Mine too...please help if you found the solution..

[@OEThe11]

In 10 Min, I came out with a better understanding of graphs then I have in the previous attempts (which was a lot). Thanks for making graphs make sense.

[@abderrahimanejjar91]

Great video!!!

[@ThiagoVieira91]

Guess I'll have a new job next month... Lately every interview has questions related to graphs.

[@sidheshwartiwari9834]

This is so interesting to learn about... Lately all I have been doing is writing layout with flex and adding event listeners .. and boii , I hate doing that..

[@skaneprime]

More videos like this please!~

[@johnnyx6654]

Not gonna lie, have an interview coming up and this was amazing, thanks so much for sharing the knowledge

[@tamasbalint1597]

Awesome! More videos like this, please. :-)

[@rishav.bharti]

A course on DSA please

[@karthikbahaddurgattematha4651]

Yes...yes...yes....yes.... Amazing!!!!!!!!!!!

[@ariunboldoyungerel6649]

Please make video explaining dynamic programming please please??

[@Sagar_RS]

This is awesome, please keep it going 👍 , need more of these .

[@evan_sarantis]

Top Content!

[@erifetim]

Can you do vim in 100 seconds? After dabbling with it for several weeks, I still don’t understand how vim (or emacs) are preferred over IDEs by so many.

[@gradientO]

Please make more of interview series. It helps us all. tan(q)