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

📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: Given a 2D array of black and white entries representing a maze with designated entrance and exit points, find a path from the entrance to the exit, if one exists.

Graph search methodologies apply well to problems that have an aspect of a spatial relationship.

Approach 1 (Brute Force)

We could try to enumerate all possible paths in the maze from the start to the finish and then check all paths to see if any of them are valid (have all white squares, aka do not run over a wall).

This is both naive and extremely costly in terms of time.

Approach 2 (Graph BFS or DFS)

We will imagine each cell as a vertex and each adjacent relationship as the edges connecting nodes.

Do we use DFS or BFS?

If we use BFS we know that the path that we find will be the shortest path because of how it searches (wide, going out layer by layer).

If we use DFS we can have the call stack remember the path making things easier to implement.

If we hit the end cell, then we will know that every call below in the call stack has a node apart of the answer path.

Since the problem just wants any path then we will use DFS since it is more straight-forward.

Complexities

Time: O( | V | + | E | )
The standard time complexity for DFS

Space: O( | V | )
We will at maximum the length of the path on the call stack through our recursion

Note: The problem on Leetcode requires BFS to pass because DFS will not always find the shortest path, but I did DFS in this video just for teaching purposes.

++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is number 19.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

[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.

[frogspawn]

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

Kudos to you!

[FrancoMunizAR]

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

[lmnefg]

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.

[betatester]

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.

[TJ-rfxl]

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!

[prinzi_piel]

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!

[abyssking]

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

[ceek]

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.

[sindisiwemncube]

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

[puncvz]

The call stack is a state! So brilliant words!

[Dunig]

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

[sairamankilambi]

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!

[thatolebethe]

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

[leelavathisettu]

Where is the code for the DFS approach

[PJ-higz]

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

[psn]

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

[darkhorse]

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

[ravitanwar]

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!

[adityamohan]

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