Free 5-Day Mini-Course:
Try Our Full Platform:
? Intuitive Video Explanations
? Run Code As You Learn
? Save Progress
❓New Unseen Questions
? Get All Solutions
Subscribe To Live Tech Offers:
Join Our Coaching Service:
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.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank:
Tuschar Roy:
GeeksForGeeks:
Jarvis Johnson:
Success In Tech:
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 19.1 in “Elements of Programming Interviews” by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
Nguồn: https://wijstaanvooronzegrondrechten.org
Xem thêm bài viết khác: https://wijstaanvooronzegrondrechten.org/cong-nghe
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.
thank you
Can you explain how to represent the maze in the form of a graph?
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.
What is the complexity of the algorithm equal?
Can anyone share the code? I was not able to find it in the description
Very interesting
Thank you so much for this! Very clear and concise explanation of DFS.
When should we go for bfs for such maze problems? Other way round, when should we go for dfs for such maze problems?
Where is the solution code please give me the link
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.
CSCI 235 brought me here
That was a very clear explaination.Keep it up ! ?
Best explanation !!
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
In worst case call stack holds all the vertices is that means it also holds the black vertices?
The video goes in-Depth of the topic literally and thus my search for DFS is complete :p
"This is the End, my friend…"
Ewedihalew !
"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
I really liked your video +1 Subscribed!!
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?
what if we can jump to diagonal?
God level
Best explanation of DFS. Thanks a lot. God bless you
you have an amazing skill of teaching, even 10 years old can understand your explanation.
Is the code posted applicable for both BFS and DFS approach?
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?
Great content! Keep up the good work!!
Hey man, after listening to your excellent explanation, I was able to go and code this up! Thanks! You are a really good teacher!