Sorry the video got cut at the end, some editing glitch :( Add the edge case at the end-> if(source.first==destination.first && source.second==destination.second) return 0; DP won't work as the value on any cell is path-dependent, so it won't work. It works in the maze which has two direction movements in the right and bottom, and the future cells would never be visited. Think about it by taking some examples. Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79
@@ankurprabhu2547 it was if(source.first==destination.first && source.second == destination.second){ return 0; } check my comment // source is the destination
why is bfs used and not dfs for finding the shortest distance between source and destination? can you explain why dp wont work in this situation.. BFS has the advantage of using priority queue and go for the nearest nodes first.. but in case if we are using normal queue can we atleast brute force the solutIion with dfs and update the nearest nodes after every dfs call for every node **if possible can you please make a video on dfs vs bfs.. to make things clear thank you** Thank you
we can use the priority queue if the we measure the distacance is the destination node minus current node and pic the node which nearest to the destination node which will reduce the time complexity.
BFS with distance on a weighted graph is Djikstra basically... so without weights just BFS with distance or Djikstra without weights ( for people asking how this comes under djikstra)
Striver sir, huge respect to you. You have given content to us which is more premium to all the paid courses. Now, I dont even have to look at the code. I can easily see what it would just after having a glimpse of the question. All thanks to you, everyone is running a bussiness of selling courses while you are giving it all for free. Thanks a lot sir
Never skip striver's video even if you have solved question by yourself. I solved this quesiton by myself using priority que without thinking pq v que here but when I watched this video I realized what I missed.
@@saibharathalam6402 you're correct, here is the edge case if(grid[source.first][source.second] == 0 || grid[destination.first][destination.second] == 0) return -1;
we can add additional check at the start if the source or destination is 0 or not since it is mentioned in the question if(grid[source.first][source.second] == 0 || grid[destination.first][destination.second] == 0) return -1; thank you striver for this amazing graph series
Bhaiya u r such a gem itna sikhaya hai aapne last k topics pe aate aate sare RUclipsr efforts ni dalte hain bhaiya lekin sach mai aapke efforts alag hee hain RUclips p videos to boht hain graph ki lekin aapki video ka wait rehta hai jb aap video upload kroge tbhi pdenge us video se thank you bhaiya placement lgne k baad aapse jrur milna hai ❤️
We can solve it using BFS. As we traverse a level add 1 to distance. Code: int shortestPath(vector &grid, pair source, pair destination) { // code here int n = grid.size(); int m = grid[0].size(); int sX=source.first; int sY=source.second; int dX=destination.first; int dY=destination.second; queue< pair< pair , int> > qu; vector visited(n,vector(m,0)); qu.push(make_pair(make_pair(sX,sY),0)); visited[sX][sY]=1; int flag = 0; int delteRow[]={-1,0,0,1}; int delteCol[]={0,1,-1,0}; while(!qu.empty()) { int i = qu.front().first.first; int j = qu.front().first.second; int dist = qu.front().second; if(i==dX && dY == j) { flag = 1; return dist; } qu.pop(); for(int x=0;x=0 && newX=0 && newY
@@rajjaiswal-tr2lk I think you are making vis[x][y] = 1 at the time of popping it, just mark the vis[x][y] = 1 at the time of inserting only and not at the time of removing it.
why is there a need for flag, I mean if you are doing flag=1, and returning, that itself ends the function, right. So the code will never proceed further after it has got flag = 1, and return;
we can use the priority queue if the we measure the distacance is the destination node minus current node and pic the node which nearest to the destination node which will reduce the time complexity.
To travel in 4 direction, we can do so without creating a direction array. Just run 2 nested loops i and j from -1 to 1 and when abs(i)!=abs(j) that means i,j is a valid direction to move.
We can solve this using deque - more optimised than using a Q. If you encounter 0, push it to the front, if 1, push it to the back. That way, the first time you encounter your destination would be your optimal cost. This pattern is called 0-1 BFS.
Amazing explanation and thanks for doing so much for the community sir, I will be very much greatfull if somebody can clarify me on the point that if we return the distance when we have reached the destination node for the first time how does it gaurantees that there is no other path shortest to it ?
We can also do it in O(1) space if we are allowed to change given input matrix , just mark the visited cells as grid[x][y]=0 hence it will never come back at this cell again
the video ends at the last terms was i think : >source is the destination if(source.first==destination.first && source.second == destination.second){ return 0; }
Can anyone explain me why we can't use dp here? We will store the minimum steps to target from every cell and then we will use the lest one !! will it not work?
yes dp using dfs can be done i.e memo but the thing is we have to find the optimal path, for dp we will be finding all the possible paths and then updating the distance each time which is unneccsary , thumb rule if we have to find shortest/optimal path use BFS
can we do the same problem just by using the queue and without the distance array like when we reach the destination we should check if the i,j == n-1,m- 1 if so we take min(ans,dis)?
to find adjacent nodes we can also do as follows(code in python3): p=[0,1,0,-1,0] for d in range(4): r1=r+p[d] c1=c+p[d+1] here r1 and c1 will be like: (0,1),(1,0),(0,-1),(-1,0) where you want to find the adjacent points of (r,c)
This question just feels like the rotten oranges question no? Except for the fact there there could be only a single rotten orange in the start (the source), and a particular fresh orange is to be affected (the destination).
For everyone saying it can be solved using simple BFS. The catch is this is 4 directional what if it was 8-directional. You would have reached the new row diagonally with 1 step lesser than you would have normally taken . That's why we need a dist matrix to keep a track of min distance that we have gone through to reach that particular node. Just dry run a matrix with 8 direction you will get what i am saying.
Recursion or dp cannot be used here because here our answer is dependent in paths, like any of the 4 directions which will give shorter path, but in dp we just bother to get our answer from any of the direction and restrict ourself going to other direction once we get our answer.
if we do this: if(r == destination.first && c == destination.second) return dis; and we write this line just after q.pop(); this doesn't fall under the edge case, tell me if I'm wrong
This is actually a BFS solution. The difference between Dijkstra and BFS is that BFS is a brute-force approach, and Dijkstra is a greedy approach. As all cell costs are the same, there is no need to consider a greedy approach here.
You can get away from using the directions matrix by just having a set of visited set with the initialized visited= set([source]) And we could do something like this new_cell = (nr,nc) if 0
We can use BFS, it is like finding min dist of a node from a source node in graph. What is the reason to use Dijsktra's algo if weights are 1 for all edges?
I agree with you. If we have different weight within edges then only Dijkastra algo...here all weights are 1 so no use of weights...we can simply go ahead with BFS and do the level order traversal like tree and once we reach destination we can that is the distance.....with every level order traversal we can increase the count..
Bhaiya can you please make a video on why DP not work in 4 direction movements, i am trying to figure it out from 1 month onwards but didnt get the reason, Thank you for wonderful Content Bhaiya
Bhai, just think at high level, while filling dp array, you use cells which are already filled up like top rows or left columns in same row, but if you would allow all possible directions, how can u calculate values for next rows and consider there values. Think for a particular index.
In the case of finding the shortest path in a matrix grid, using a brute-force approach to explore all possible paths and return the minimum distance does not exhibit the overlapping subproblem structure or optimal substructure that DP problems usually possess. Each path exploration is independent and does not build upon previously computed results.
Why do we return at the time when we found the destination ?Why did not we traverse till the queue completes and then return the dist from distance array ?
bhayiya isme like iterate karte hue aisa nahi ho sakta ki kisi aur path se aur minimum path aa jaye toh humko jab q.front() pe ans mile tab distance return karna chayiye
What if we use Priority Queue for minimum distance between destination and current point , By this we are greedy about the destination's position from current point, i am assuming this will reduce time complexity for this problem, because in this manner our priority Queue size will be smaller , so log n time for getting the element or adding will not cost more. please provide your observation on this @takeUforward
Why are you returning answer on the moment you got the end row and end col??? Why aren't you checking "if there exist any other path from where we can reach here with less distance and return in the end of bfs"???
distance will always increase if we further continue the bfs algorithm. Whenever, first time we find our destination, we can return because this is indeed the minimum distance from src to dest
Sorry the video got cut at the end, some editing glitch :(
Add the edge case at the end->
if(source.first==destination.first && source.second==destination.second)
return 0;
DP won't work as the value on any cell is path-dependent, so it won't work. It works in the maze which has two direction movements in the right and bottom, and the future cells would never be visited. Think about it by taking some examples.
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
Sir the video is incomplete check the last minute u were going to say something but the video finished already
@@ankurprabhu2547
it was
if(source.first==destination.first && source.second == destination.second){
return 0;
} check my comment
// source is the destination
why is bfs used and not dfs for finding the shortest distance between source and destination?
can you explain why dp wont work in this situation..
BFS has the advantage of using priority queue and go for the nearest nodes first.. but in case if we are using normal queue can we atleast brute force the solutIion with dfs and update the nearest nodes after every dfs call for every node
**if possible can you please make a video on dfs vs bfs.. to make things clear thank you**
Thank you
I guess we don't need this edge case, as we are already initializing in the start dist[source.first][source.second] = 0
we can use the priority queue if the we measure the distacance is the destination node minus current node and pic the node which nearest to the destination node which will reduce the time complexity.
BFS with distance on a weighted graph is Djikstra basically... so without weights just BFS with distance or Djikstra without weights ( for people asking how this comes under djikstra)
Yeah !! I also figured it out man !! Thanks btw...
The intuition of using a queue instead of priority queue was amazing
This is not an intuition vo normal bfs hai😅
@@pratik.784 true bro that is what i want to say
why we didnt used set? like every time we insert we will insert a new element so it should also work no?
@@harshitmalik486 Unnecessary added overhead on TC. Because its unit length, queue works fine.
na, the intution of using Priority Queue in a simple BFS question was amazing
Striver sir, huge respect to you. You have given content to us which is more premium to all the paid courses. Now, I dont even have to look at the code. I can easily see what it would just after having a glimpse of the question. All thanks to you, everyone is running a bussiness of selling courses while you are giving it all for free. Thanks a lot sir
This can be solved using BFS. Keeping count of the distance. If we find the destination then we return the dist else return -1 if the bfs ends
it's a BFS only don't get confused by fancy names understand the working
dijkstra itself is bfs
The exact comment and the exact reply I was looking for
dijkstra is also fancy bfs
@@jeeveshpathak2808 Haha , U guys are not catching the concept , Conventional BFS does not use Distance array. Although BFS can be used here.
Understood. I am now slightly more confident in graph after watching your videos and doing a dry run myself💯💪.
Never skip striver's video even if you have solved question by yourself. I solved this quesiton by myself using priority que without thinking pq v que here but when I watched this video I realized what I missed.
EDGE CASE:
if(source.first==destination.first && source.second==destination.second)
return 0;
This edge case handling won't be required if you put the destination check before exploring the neighbors.
I think that is not the edge case . The edge case is what if source position has 0 instead of 1 then we can directly return -1
@@saibharathalam6402 you're correct, here is the edge case
if(grid[source.first][source.second] == 0 || grid[destination.first][destination.second] == 0) return -1;
@@AbhishekKumar-yv6ih yeah bro i did it this way
we can add additional check at the start if the source or destination is 0 or not since it is mentioned in the question
if(grid[source.first][source.second] == 0 || grid[destination.first][destination.second] == 0) return -1;
thank you striver for this amazing graph series
Huge respect! The intuition of using a queue is so thoughtful. My journey of problem solving is getting more interesting with your videos.
Bhaiya u r such a gem itna sikhaya hai aapne last k topics pe aate aate sare RUclipsr efforts ni dalte hain bhaiya lekin sach mai aapke efforts alag hee hain RUclips p videos to boht hain graph ki lekin aapki video ka wait rehta hai jb aap video upload kroge tbhi pdenge us video se thank you bhaiya placement lgne k baad aapse jrur milna hai ❤️
Striver is slowly helping me remove my fear of graphs and dp
One of the best in entire youtube.
Did without watching the video, just by watching the problem explanation. Thanks Striver.
At last 20:43 he was telling that if the source and destination is same then it is the edge case where we have to return 0 :)
Checking for node==destination just after popping it from the queue should cover that case
Solved without watching the video . ThankYou sir.. for making our concepts crystal clear.
We can solve it using BFS. As we traverse a level add 1 to distance.
Code:
int shortestPath(vector &grid, pair source,
pair destination) {
// code here
int n = grid.size();
int m = grid[0].size();
int sX=source.first;
int sY=source.second;
int dX=destination.first;
int dY=destination.second;
queue< pair< pair , int> > qu;
vector visited(n,vector(m,0));
qu.push(make_pair(make_pair(sX,sY),0));
visited[sX][sY]=1;
int flag = 0;
int delteRow[]={-1,0,0,1};
int delteCol[]={0,1,-1,0};
while(!qu.empty())
{
int i = qu.front().first.first;
int j = qu.front().first.second;
int dist = qu.front().second;
if(i==dX && dY == j)
{
flag = 1;
return dist;
}
qu.pop();
for(int x=0;x=0 && newX=0 && newY
Exactly it is like finding min dist of a node from a source node in graph. What is the reason to use Dijsktra's algo if weights are 1 for all edges?
bhai mene same method apply kia GFG pe, time limit exceeded aa rha, I don't know why
@@rajjaiswal-tr2lk I think you are making vis[x][y] = 1 at the time of popping it, just mark the vis[x][y] = 1 at the time of inserting only and not at the time of removing it.
Bro Dijkstra is nothing different its just extended version of BFS for weighted edges. Try to keep things as simple as you can. It makes life easier.😀
why is there a need for flag, I mean if you are doing flag=1, and returning, that itself ends the function, right. So the code will never proceed further after it has got flag = 1, and return;
OHHH! MANNN!!!
I SOLVEDD IT ALONNNEEE!!! I will now watch the video!! Striver, bhai, you taught us well!!!!
Thank you striver , for this graph series , I did this que by myself , thanks to your fabulous Teaching .
Without even starting the video, I did it on my own and it was correct in the first attempt itself. Thank You Striver😊
Understood !!!!! Watched the entire DP Series, Recursion Series and now soon will mark the whole graph series too....💯
watch free ka tree series
we can use the priority queue if the we measure the distacance is the destination node minus current node and pic the node which nearest to the destination node which will reduce the time complexity.
20:40
the edge case will :
if ( grid[rowSource][colSource] == 0){
return -1; }
also if destination is 0 you can return -1 since it is not reachable
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
To travel in 4 direction, we can do so without creating a direction array. Just run 2 nested loops i and j from -1 to 1 and when abs(i)!=abs(j) that means i,j is a valid direction to move.
We can solve this using deque - more optimised than using a Q. If you encounter 0, push it to the front, if 1, push it to the back. That way, the first time you encounter your destination would be your optimal cost. This pattern is called 0-1 BFS.
great work by you sir...understood the concept🤩
UnderStoood Bhaiya , such a smooth learning experience we get through your teaching
Amazing explanation and thanks for doing so much for the community sir, I will be very much greatfull if somebody can clarify me on the point that if we return the distance when we have reached the destination node for the first time how does it gaurantees that there is no other path shortest to it ?
Understood! So amazing explanation as always, thank you very much!!
We can also do it in O(1) space if we are allowed to change given input matrix , just mark the visited cells as grid[x][y]=0 hence it will never come back at this cell again
Understood. Who ever coming directly please do the whole graph series from beginning. It will be pretty simple to do then.
instead of making 2 separate arrays for row and column simply do
vector delta = {0,1,0,-1,0};
int n=delta.size();
for(int k=0 ; k
int dir[4][2] = {{-1 , 0} , {0 , -1} , {1 , 0} ,{0 , 1}};
Can we do this via BFS as this same as unweighted graph so that our complexity reduces to O(V+E) ??
yup
it is a matrix, not adjacency list
so complexity will be O(m*n)
the video ends at the last terms was i think :
>source is the destination
if(source.first==destination.first && source.second == destination.second){
return 0;
}
Awesome ...btw It's pure BFS 😀
Bow my head...i solved the leetcode one in 1 go with your 8 direction move concept of...delx and dely
pls send the code here
I solved it without even watching the video. Normal question of exploring all 4 directions and applying dijkstra.
ap smart ho na
wonderful explanation
This can also be easily solved with BFS approach right(since the edge weights are considered 1)
Can anyone explain me why we can't use dp here?
We will store the minimum steps to target from every cell and then we will use the lest one !! will it not work?
dp too uses bfs type of traversal if you perform and its safe to say that this is a problem of bfs rather than of djikstra
yes dp using dfs can be done i.e memo but the thing is we have to find the optimal path, for dp we will be finding all the possible paths and then updating the distance each time which is unneccsary , thumb rule if we have to find shortest/optimal path use BFS
Checking if Source is Destination ----- *if (source == destination) return 0;*
Was able to solve it, just by seeing the previous video, thanks!
can we do the same problem just by using the queue and without the distance array
like when we reach the destination we should check if the i,j == n-1,m- 1 if so we take min(ans,dis)?
to find adjacent nodes we can also do as follows(code in python3):
p=[0,1,0,-1,0]
for d in range(4):
r1=r+p[d]
c1=c+p[d+1]
here r1 and c1 will be like: (0,1),(1,0),(0,-1),(-1,0) where you want to find the adjacent points of (r,c)
Why queue is used instead of PQ is the realisation point, the "ooo...." moment!
what will be the time complexity ??
This question just feels like the rotten oranges question no? Except for the fact there there could be only a single rotten orange in the start (the source), and a particular fresh orange is to be affected (the destination).
yes
understood, thanks for the great video
Thank you sir 😊
This can be solve by just counting the level that we treversed untill the destination reach(Multisource BFS) , without use of Dijkstra concept
there's only one source
This can be solved using BFS too, right?
Oh wait we are using queue and this approach is effectively BFS only
path relaxing + BFS
yes...solved it just using bfs...nothing else.....(if weights are 1 then BFS will always give the shortest path)
@@MrAnyzen no need of path relaxing ,which ever reach first will be its minimum distance
@@Rahul-rp5hk Yes...
For everyone saying it can be solved using simple BFS. The catch is this is 4 directional what if it was 8-directional. You would have reached the new row diagonally with 1 step lesser than you would have normally taken . That's why we need a dist matrix to keep a track of min distance that we have gone through to reach that particular node.
Just dry run a matrix with 8 direction you will get what i am saying.
yes BFS won't work for 8 direction kyuki 2 node ke connect krne ka abb distance ab variable hogya
leetcode code pe hai 8 directions wla
But the bfs algo is working for leetcode 8 direction question I tried it
I think if we are given uniform weights we should use plain bfs in the cases where there is non uniform weights we should use dijkstra algo
Why cant we use the recursive or dp approach here ??
same doubt
Recursion or dp cannot be used here because here our answer is dependent in paths, like any of the 4 directions which will give shorter path, but in dp we just bother to get our answer from any of the direction and restrict ourself going to other direction once we get our answer.
Sir,this problem can be solved with simple bfs?
We return the answer one we reach at destination but what if we get any other shorter path after going through another way.?
if we do this:
if(r == destination.first && c == destination.second) return dis;
and we write this line just after q.pop();
this doesn't fall under the edge case, tell me if I'm wrong
This is actually a BFS solution. The difference between Dijkstra and BFS is that BFS is a brute-force approach, and Dijkstra is a greedy approach. As all cell costs are the same, there is no need to consider a greedy approach here.
thank you
Unterstood bhaiya ,amazing explanation and also thanks bhaiya for provide such as quality lecture free :-)
Understood very well!!!!!!!!!!!!!
You can get away from using the directions matrix by just having a set of visited set with the initialized visited= set([source])
And we could do something like this
new_cell = (nr,nc)
if 0
Great video sirji
Understood Sir, Thank you very much
We can use BFS, it is like finding min dist of a node from a source node in graph. What is the reason to use Dijsktra's algo if weights are 1 for all edges?
I agree with you. If we have different weight within edges then only Dijkastra algo...here all weights are 1 so no use of weights...we can simply go ahead with BFS and do the level order traversal like tree and once we reach destination we can that is the distance.....with every level order traversal we can increase the count..
@@ravipatel-xu5qi Yes
Can I convert the adj matrix into adj list and run a dfs from (0,0) ?
Bhaiya can you please make a video on why DP not work in 4 direction movements, i am trying to figure it out from 1 month onwards but didnt get the reason, Thank you for wonderful Content Bhaiya
Bhai, just think at high level, while filling dp array, you use cells which are already filled up like top rows or left columns in same row, but if you would allow all possible directions, how can u calculate values for next rows and consider there values. Think for a particular index.
Bro explain me more briefly ....
@@dhirisalasaisankar4338 there should not be cyclic dependency in the reccursion tree for DP to work properly
In the case of finding the shortest path in a matrix grid, using a brute-force approach to explore all possible paths and return the minimum distance does not exhibit the overlapping subproblem structure or optimal substructure that DP problems usually possess. Each path exploration is independent and does not build upon previously computed results.
Can be solved by simple BFS as there is edge weight.
Understood Bhaiya😊😊
Understood bhaiya.
Can't we use dfs to solve this problem?
I don't understand why dp won't work can any one please explain
We can solve this using a simple BFS also right ? just keep a counter for very level traversal from source to destination. Tell me if I am wrong here
I guess BFS is in fact better here coz this is an unweighted graph actually! So we don't need the extra distance array as well if we use normal BFS!
also "Dijkstra using queue" is nothing but BFS only
yes bro..keep a counter ,increase after visting every level
understood sir
Understood !🤩🤩🤩
Please explain can we use simple bfs here? Why we need to store distance in priority queue?
we're using queue here
Understood understood understood
ok
Thank you very much. You are a genius.
Why do we return at the time when we found the destination ?Why did not we traverse till the queue completes and then return the dist from distance array ?
because the queue is arranged in incremental order of distances. So, we need not to traverse till end of the queue.
Thank you bhaiya
understood , if source== destination return 0;
Understood sir 🙂
bhaji tuc great ho
bhayiya isme like iterate karte hue aisa nahi ho sakta ki kisi aur path se aur minimum path aa jaye toh humko jab q.front() pe ans mile tab distance return karna chayiye
On 8:11 the key of solving this question lies. Really it was lil hard to fugure it out with own
Understood
What if we use Priority Queue for minimum distance between destination and current point , By this we are greedy about the destination's position from current point, i am assuming this will reduce time complexity for this problem, because in this manner our priority Queue size will be smaller , so log n time for getting the element or adding will not cost more.
please provide your observation on this @takeUforward
hmmm cant we done it using simple BFS?
edge case bhaiya is saying in end
if(source.first==destination.first && source.second==destination.second)
return 0;
us
Why are you returning answer on the moment you got the end row and end col??? Why aren't you checking "if there exist any other path from where we can reach here with less distance and return in the end of bfs"???
distance will always increase if we further continue the bfs algorithm. Whenever, first time we find our destination, we can return because this is indeed the minimum distance from src to dest
Aren't we returning the answer when we reach the target cell coz the distance of travelling from one cell to another is not variable.
Why DP not work here .....?
Striver here the shortest path is 2 right in the example, go right then down then down ...
That is still 3, and you cannot go right anf then down because of 0
@@takeUforward understood thanks
iski tc kitni huyi pls explain ,, agar dijstra is same like bfs in this so elogv huyi ya e+v????????????
Why dfs won't work???
The video got cut at last.
Understood 👍
i guess we can also use BFS here, because BFS also promises to give us the shortest path
yes, BFS is right
Understood.🎉
Understood.
Understood!