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

[@BackToBackSWE]

Table of Contents: Leave The Library Plz 0:00 - 0:17 The Problem Introduction 0:17 - 2:50 Our Fundamental Operations 2:50 - 3:50 Beginning The Depth-First Search 3:50 - 7:26 We Hit Dead End #1 7:26 - 9:50 We Get Back On Track 9:50 - 12:03 We Hit Dead End #2 12:03 - 13:27 We Get Back On Track Again 13:27 - 14:31 We Reach Our Target: The End 14:31 - 15:00 Returning Back Upwards With The Path 15:00 - 15:28 The Top Level Caller Gets The Path 15:28 - 15:59 Time Complexity 15:59 - 16:42 Space Complexity 16:42 - 17:09 Wrap Up 17:09 - 17:30 The code for this problem is in the description. Fully commented for teaching purposes.

[@amirmohideen99]

code is missing

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now

[@punitpawar4231]

@@BackToBackSWE Is it possible for you to share the link to this code ?

[@Thadnill]

@@punitpawar4231 I wonder this as well

[@UECDishaKhattri]

yes it would be wonderful if you just provide the code link

[@frogspawn8]

Bruh, your lectures are WAY clearer and more concise than some of the “best” professors I’ve encountered. Kudos to you!

[@BackToBackSWE]

thx

[@ers-br]

I thought he was a professor ... and he's just a student. Really good explanations.

[@FrancoMunizAR]

You and Abdul Bari are the kings of explaining algorithms and problem solving. Thanks a LOT for everything you do!

[@johnbanyan11]

Damn true

[@jst8922]

NeetCode, DEEPTI TALESRA, Jenny's Lectures CS IT, Tushar Roy - Coding Made Simple, Nikhil Lohia too.

[@lmnefg121]

I really like that you explain things in such a simple way and teaches the most fundamental method. As a matter of fact, it is always most difficult to learn the most fundamental stuff.

[@BackToBackSWE]

thanks.

[@betatester03]

Man, you are an excellent teacher. I stumbled onto one of your videos earlier and immediately started up another, right after. I'm about five videos in, now. I've got books upon books about algorithms, I've read articles, related papers, tutorials, pseudo-code implementations, and public code-bases on software repo's, but this is the first time I've gained a simple, clear intuition for some of these concepts. Thank you so much for taking the time to make these videos. I'll refer people to your content any chance I get.

[@BackToBackSWE]

Sure - thank you.

[@TJ-rf1xl]

Best explanation I've seen of DFS so far. I wish my professors explained things this way. I likely would have dropped out of my MSc if it wasn't for your channel!

[@BackToBackSWE]

dang, nice!

[@GraniLP]

Big thanks to you! Currently I am a bit angry that my university is not capable of explaining such stuff in a nice way, but you did it in less time and in a much clearer way!

[@sindisiwemncube4665]

This dude is a brilliant tutor. Never have i ever understood an algorithm this clearly, Juss did.

[@abyssking4062]

Till now, your video is still saving lives. I finally completed my damn maze assignment after your explanation. Wherever you are bro, THANK YOU!!!

[@qiuyangshen3569]

The call stack is a state! So brilliant words!

[@BackToBackSWE]

ye

[@deepusasidharan2012]

Yes...it cud be completed or uncompleted(waiting for child stack to complete)

[@ceek79]

Honestly, you sitting in front of a computer would be a waste of talent! Take advantage of your skill to explain complex stuff the easy way and make a business out of it.

[@BackToBackSWE]

👀👀💰💸💰

[@jonathandaniel7321]

@@BackToBackSWE start a university with only you as teacher

[@BackToBackSWE]

@@jonathandaniel7321 I do not want to do that.

[@Dunig2]

This is so clear to me, I’m amazed at how easy you make this to understand

[@BackToBackSWE]

nice

[@sairamankilambi5007]

I saw the BFS & DFS (15 min) video followed by the maze problem. Wow! It clears out when and where to chose BFS over DFS. Thanks a LOT!

[@BackToBackSWE]

sure

[@ravitanwar9537]

hey man , i'm the one who asked for minimum window substring on leetcode . just wanna tell you that you doing a pretty good job and this channel HAS the potential. keep coming up with these videos and if possible with python language . cheers!

[@BackToBackSWE]

hmmmm, yeah, good idea. I need to brush up on my Python though. My languages in order of strength: Java, Typescript (a superset of course), Javascript ...then some experience with C, C#, Ruby

[@ravitanwar9537]

@@BackToBackSWE n i think it'll also be a good idea if you specify the difficulty level before the video . for eg :- easy , medium , hard on leetcode ,

[@BackToBackSWE]

@@ravitanwar9537 Every video has badges of the difficulty.

[@darkhorse621]

Best Explanation for DFS I've come across so far. Thanks a lot !!! Keep up the good work guys.

[@BackToBackSWE]

thx

[@thatolebethe8896]

Dude thanks for thee constant repition. Really helped cement how depth first search works

[@BackToBackSWE]

Glad to hear that! explore our 5 day free mini course for some cool content - backtobackswe.com/

[@psn999100]

WOW. best explanation so far. After this I am gonna do Maze I, II and III on Leetcode. I got asked this for Amazon OA and i screwed up cuz my fundamentals were not good. thanks

[@BackToBackSWE]

nice and sure

[@Hav0c1000]

Hey man, after listening to your excellent explanation, I was able to go and code this up! Thanks! You are a really good teacher!

[@BackToBackSWE]

sure

[@darod6098]

Just amazing. I'm really grateful for your work

[@BackToBackSWE]

long way to go...very very very very long way

[@xxbighotshotxx]

@@BackToBackSWE Don't forget to enjoy the journey :)

[@PJ-hi1gz]

bro you explain so clear, it's a wonderful gift to have and share with others

[@shubhamk840]

you have an amazing skill of teaching, even 10 years old can understand your explanation.

[@BackToBackSWE]

thanks

[@erinkerciku]

I don't usually leave likes on videos but you deserve it my guy.

[@kgopotsomasela4627]

Your patience is admirable

[@alikizander]

Your delivery and presentation is just on POINT. I don't like it, I LOVE IT. You helped me tackle a PACMAN PROBLEM USING THE UNIFORM-COST SEARCH BY JUST WATCHING THIS VIDEO

[@sanctusfides]

"Can I go up, yes I can!" is going to be looping in my head for a week after this video

[@maharshidave4472]

Hello, sir you have high degree of patience to expain each and every minute detail. And I wish you will soon reach your traget of 100K subscribers and keep it up.😀

[@BackToBackSWE]

thx

[@banelemakhanya2595]

​@@BackToBackSWE hi, would love help on mazes

[@ritwik121]

the visualizations are really fantastic. awesome work ben :)

[@BackToBackSWE]

thx

[@stephentanksleymusic7240]

This was fantastic. Thank you so much for such a clear, effective explanation of recursive DFS algorithms for maze traversal!

[@BackToBackSWE]

sure!

[@ebiigweze3384]

"AND NOW WE ARE THIS CELL" ........that is a drinking game right there...number of times that was said, man would be wasted in no time...cool tutorial bro .. keep it up

[@BackToBackSWE]

hahahahahahaha

[@vrdash]

The video goes in-Depth of the topic literally and thus my search for DFS is complete :p

[@BackToBackSWE]

nice

[@pavel9652]

This is the library floor plan. The library will be closing in 15 minutes. Implement one of the fundamental graph searching algorithms (DFS/BFS) to find the exit from the building ;)

[@BackToBackSWE]

yes

[@siddhantrai7529]

One of the best explanation of maze problem... Beautiful

[@BackToBackSWE]

thanks

[@jkim5118]

What's the main pros and cons of doing this in BFS and DFS? I thought DFS would be better, but it seems like only BFS is accepted on Leetcode. What are your thoughts? Also, do you think we should also know how to do Dijkstra for these kinds of search questions but with weights?

[@BackToBackSWE]

BFS always finds the shortest path. The reason DFS times out is because it will get really far from the answer and waste time. BFS will find the object faster...generally...think about it...BFS goes out level by level and doesn't go deep into anything. This is good and bad. Ponder on these things.

[@zackgrey4472]

Beautiful video, you just earned a subscriber. I really admire your content!!!

[@BackToBackSWE]

thx

[@goldfishbrainjohn2462]

This helped me a lot!! I love the way you teach. Thanks. Subscribed immediately Edit: The code below is my version of DFS for a maze problem and the concept is based on this video. Appreciate it. function solve(lines) { let wAndH = lines.shift(); wAndH = wAndH.split(' '); let [w, h] = wAndH; w = Number(w); h = Number(h); let nestedArr = lines.map(item => { let a = []; a.push(item); return a; }) nestedArr = nestedArr.map(item => { return item[0].split(""); }) let blockStart = []; let blockEnd = []; for(let i = 0; i < w; i++){ blockStart.push('#'); blockEnd.push('#'); } nestedArr.splice(0, 0, blockStart) nestedArr.splice(h+1, 0, blockEnd); nestedArr.forEach(item => { item.unshift('#'); item.push('#'); }) let roadCoordinates = []; function findRoad(arr = [], h = 0, w = 0, road) { const checkUp = (arr, h, w) => { if(arr[h-1][w] === '.') { return true; } else { return false; } } const checkRight = (arr, h, w) => { if(arr[h][w+1] === '.') { return true; } else { return false; } } const checkDown = (arr, h, w) => { if(arr[h+1][w] === '.') { return true; } else { return false; } } const checkLeft = (arr, h, w) => { if(arr[h][w-1] === '.') { return true; } else { return false; } } if(arr[h] != 'undefined') { if(arr[h][w] === '.') { if(checkUp(arr, h, w)) { arr[h][w] = '1'; road.push([w,h]) findRoad(arr, h-1, w, road); } else if(checkRight(arr, h, w)) { arr[h][w] = '1' road.push([w,h]) findRoad(arr, h, w+1, road); } else if(checkDown(arr, h, w)) { arr[h][w] = '1' road.push([w,h]) findRoad(arr, h+1, w, road); } else if(checkLeft(arr, h, w)) { arr[h][w] = '1' road.push([w,h]) findRoad(arr, h, w-1, road); } else if(arr[h][w] === '.') { arr[h][w] ='1'; road.push([w,h]) } } else { console.log('Wrong') } } } findRoad(nestedArr, 1, 1, roadCoordinates) nestedArr.pop(); nestedArr.shift() nestedArr.forEach(item => { item.pop(); item.shift() }) roadCoordinates.pop(); console.log(roadCoordinates.length) }

[@BackToBackSWE]

great, thanks, sure, and great

[@adityamohan393]

Amazing explanation, but not able to find the code in the description.

[@ryangallagher1285]

The best explanation on the internet.

[@BackToBackSWE]

That's nice of you

[@erichlf]

Amazon asked me this in the phone interview and even though I knew it I promptly fucked it up.

[@BackToBackSWE]

Eh, whateves

[@wrestlingscience]

absolutely no one: backtobackswe: can i go up yes can i go up yes can i go up no

[@HemanthaKumarYadav]

The way you explain is simply amazing sir!

[@studyonline3236]

client, at the end of a successful dfs, to node at the start: Yo got the result? start node : yes client: What did it cost? node: realisation at 9:50 and 13:31

[@BackToBackSWE]

wut lol

[@无名字-q7k]

Thanks! this is useful, im currently making a game which npc will randomly trigger travel event, but i need the npc to calculate the clear path to the end and avoid crash into rock and hill 😂

[@leelavathisettu2762]

Where is the code for the DFS approach

[@anssha2643]

Best explanation of DFS. Thanks a lot. God bless you

[@BackToBackSWE]

sure

[@ShikharKumar-fz6ti]

Amazing video, do you have one of these Maze path for BFS, A*, Uniform Cost Search?

[@kirillzlobin7135]

Maaan, you are the legend. Thank you for your brilliant explanation!!!

[@BackToBackSWE]

Happy Halloween 🎃 Thank you from one legend to another, kirillzlobin! You get some extraaa treats - 50% Off our exclusive lifetime membership use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50

[@umairbijapure7584]

U hv given a greatest explanation i ever had on KZbin..but implementation is also important right..plz do explain codes as well

[@lifecodesher5818]

this man is international version of sumeet sir of pepcoding

[@BackToBackSWE]

what lol

[@fmpwizard]

Awesome explanation! Very clear and the right amount of details

[@jefferyxie3248]

Thanks so much for the video! This makes so much more sense now

[@multichannellk1966]

Where is the solution code please give me the link

[@BackToBackSWE]

The respository is deprecated - we only maintain backtobackswe.com now.

[@andyhujian]

Good talk. But it's different from maze leetcode. In leetcode problem, it can't choose directions at will. It needs to hit a wall before making a turn.

[@BackToBackSWE]

ok

[@santasingh9045]

take a bow,man!

[@BackToBackSWE]

bow

[@julianbullmagic]

keep posting videos, I would love to see more of this

[@BackToBackSWE]

ok will do

[@mariasandru7]

What if we wanted to search for all the possible paths? I am talking about the Unique Paths III problem on Leetcode. Amazing video btw!

[@BackToBackSWE]

We can just do a DFS and imagine this as a tree. The "leaf" is the end, we keep track of the path up to the end then add it as an answer, then backtrack, and if we reach the end again we again register the different way we got there.

[@mariasandru7]

@@BackToBackSWE Thank you! I got accepted from the first submission:D

[@BackToBackSWE]

@@mariasandru7 nice

[@richardaguilar7692]

Thank you so much for this! Very clear and concise explanation of DFS.

[@BackToBackSWE]

sure

[@aliceabejo8044]

What the decimals please?

[@Yusifinify]

Brilliant - clear and concise!

[@ramraut180]

The great video. Thank you so much for your contribution. Keep continuing making this type of video. Thumbs up !

[@BackToBackSWE]

sure

[@toyadavrahul]

Great Explanation!! would be better with some pseudo code!! Else found it really helpful. Thanks!!

[@BackToBackSWE]

nice

[@267praveen]

Ques - why we didn't chose BFS here? And what was the reason behind chosing DFS? You did mention that BFS gives shortest path but then switched to DFS. Can you please shed some more light?

[@manurajput5348]

Hey can you explain why the time complexity is V+E. We are checking 4 (i.e. E) edges for each vertices(V). So shouldn't the complexity be 4V i.e. V.E?

[@svdfxd]

Awesome explanation. Keep up the good work. Do you have a concise list of Algorithms that we must study? I have gone through udemy courses but there are many many algorithms. It would be good if there is a list which lists all important algorithms.

[@BackToBackSWE]

For interviews or to become a great computer scientist? For interviews check this readme: github.com/bephrem1/backtobackswe To become a great computer scientist I'm not totally sure. There is too much to cover here in one comment.

[@svdfxd]

For the interviews :). Thanks a lot.

[@BackToBackSWE]

@@svdfxd Yeah, read EPI. Watch all Hacker Rank videos on KZbin. And....watch my videos in the coming months :)

[@lawlietnao_music]

dude I hecking love you, if I get the offer I'll definitely donate the shit out of u

[@BackToBackSWE]

Don't, just get the offer.

[@zackzayco9135]

Great information 💪🏽💯 I appreciate it

[@atmafra1971]

Very helpful, thanks a lot!

[@promamukherjee5874]

If I'm not mistaken, this approach is backtracking, right? And its complexity is to the exponential order of 2^(n*m) where n*m is the order of the matrix, but for a vanilla DFS we should have linear complexity, O(m*n)

[@kyawn5115]

Great content! Keep up the good work!!

[@BackToBackSWE]

ok

[@akhilk5121]

I am confused. You said in your bfs,dfs fundamentals that bfs can be used to check "if a path exist" . Here you said bfs is going to give the shortest path so its better to use dfs to find "if a path exist". What did i miss?

[@BackToBackSWE]

Both can be used for path search

[@MdMainuddinJU]

Subscribed the channel, Liked the video, it deserves it.

[@jonaurz]

you explained so well, thank you!

[@BackToBackSWE]

sure

[@exkorbuto1]

Well, I had a similar problem but there can be too many paths, that adds complexity. And I had to choose the shortest.

[@BackToBackSWE]

nice

[@sidb8066]

Hey! Great video! What;s the difference between DFS and Backtracking on this problem? Cant both be used and wont both work the same way?

[@BackToBackSWE]

DFS is a search methodology. Backtracking entails looking at candidate solutions in an exhaustive way (often following a search path) and "backtracking" to abandon partial solutions once they can't lead to a final solution. Both can happen at the same time. Example: "Search a graph for paths from the start to the end with cost < 100, no nodes have a negative cost." If I am on a path and my cost hits 140 I could be deep into a path (if I am using DFS) but I'd backtrack to the previous node I was at since I can't recover (i shouldn't have stepped on the next node in the first place but you get the idea).

[@martinharris4416]

OMG YOU'RE SOOO DEEEEP

[@BackToBackSWE]

ok

[@rizzbod]

this is amazingly amazing explanation. thnx buddy

[@jeffreyslominsky7656]

Thank you, your explanations are great!

[@BackToBackSWE]

sure and thanks

[@drizle9231]

That was a very clear explaination.Keep it up ! 😊

[@BackToBackSWE]

ok

[@chrisliu5403]

appreciate it man, well explained.

[@BackToBackSWE]

sure

[@adrizamishra7568]

Thank you for saving us!

[@althafa8371]

atlast i found non indian tutorial :P , good explanation bro

[@BackToBackSWE]

ye, indians r brothers tho

[@dinner4chiahao]

Your vids are brilliant.

[@nanamahmoud147]

I want to ask how did you decide the order of the operations "up","right","left",down" , is it because you compared the starting cell and the goal/end cell and found out you should prioritize "up" and "right" operations ? so thats why they are at the top of the order of the operations and you check on them first?

[@nanamahmoud147]

and can you please provide me the of the code that corresponds to this problem

[@niddynoddy]

I'm currently having a problem with implementing DFS in ruby, and have had it for a week now. Is there a way to get the code out of this video anymore?

[@rubaiyathussain3124]

Thank you. i fully grasp it.

[@BackToBackSWE]

nice

[@Thadnill]

If I want to use the DFS to generate a maze in C++, and not necessarily solve it, how should I think and start out? Thanks for the great video!

[@BackToBackSWE]

sure and you can google that?

[@maxinteltech3321]

Awesome explanation

[@shathamaayouf6048]

I need you to switch positions with my German lecturer

[@BackToBackSWE]

hahahaha

[@rishabhmalhotra2225]

Can you explain how to represent the maze in the form of a graph?

[@BackToBackSWE]

cell is a node, edges are the 4 adjacent walls

[@Thadnill]

Woa, you just got my sub! P.S do you have the code available? I can't find it

[@BackToBackSWE]

Thanks, and the code repository is deprecated - we only maintain backtobackswe.com now.

[@gk79797]

Awesome explanation sir!!!

[@BackToBackSWE]

sure

[@deepusasidharan2012]

Great Visulazation material....Please draw a small CallStack as well.....

[@alanye7542]

So amazing! Thanks!

[@dongshuowu3454]

Amazing as usual.

[@BackToBackSWE]

thanks haha

[@algorithmimplementer415]

May I ask, if you are given an adjacency matrix of m x m, in that case what would be the time complexity of DFS path finding algorithm? Could you also explain?

[@BackToBackSWE]

Sure, this search should give you what you need: www.google.com/search?q=DFS+with+adjacency+matrix+time+complexity&oq=DFS+with+adjacency+matrix+time+complexity&aqs=chrome..69i57j0l5.7645j1j7&sourceid=chrome&ie=UTF-8

[@parthsohani2429]

When should we go for bfs for such maze problems? Other way round, when should we go for dfs for such maze problems?

[@BackToBackSWE]

bfs - wide, shortest path dfs - deep, any path finding

[@asifulhaque4026]

Best explanation🖤

[@prodbyCheez]

and now we are at this cell

[@shikharsaxena4432]

At one point in this video, I was wondering whether Canwegoup is a word.

[@BackToBackSWE]

lol what

[@greaper3180]

I wish you were my teacher in university.

[@jupaol]

Can anyone share the code? I was not able to find it in the description

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@shivams417]

clear explanation

[@BackToBackSWE]

thx