Shortest Path in Binary Matrix | Live Coding with Explanation | Leetcode - 1091

This video shows the BFS method to solve shortest path in binary matrix leetcode 1091.

To support us you can donate

Check out our other popular playlists:

If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful.

#coding #leetcode #programminglife #programmingisfun #programmer #tech #software #codinglife #leetcode

[AlgorithmsMadeEasy]

We hope you all are enjoying our videos!!! Don't forget to leave a comment!!! Please like the video to support us!!!

Questions you might like:

Struggling in a question??

Leave in a comment and we will make a video!!!🙂🙂🙂

[sc.smitshah]

Thank you. You videos are helping me succeed in a hope that i can master DSA! Appreciate this. Hope you continue on this.

[vishweshpujari]

Very good explanation. However in this problem there is no need to do the BFS one level at a time. So the while (size-- > 0) loop can be totally removed.

[bnetjail]

Awesome video! Your English is extremely comprehensible by the way.

[monikachaudhary]

very nice. You made it easy to understand. Thanks.

[akashingale]

Given a boolean 2D matrix (0-based index), find whether there is path from (0, 0) to (x, y) and if there is one path, print the minimum no of steps needed to reach it, else print -1 if the destination is not reachable. You may move in only four direction ie up, down, left and right. The path can only be created out of a cell if its value is 1. how to solve this qustion

[vastauine]

what's the time/space complexity here, I'm assuming O(mn) since its iterating over m*n grid ignoring direction for loop since its constant/fixed

[rechinraj]

Is it shortest path logic OR just path ?? Not able to understand how come it's calculating only shortest path ?

[jayantshukla]

Mam how are we getting the shortest path when we are not comparing? Please tell

[sharoonaustin]

Space complexity could be reduced by changing the value of the grid elements from 0 to -1.

[satyamjha]

Mam, why are you using while(size-->0)? I have done without inner while loop than my only 50% test case ran.

class Solution {
public int grid) {
int m=grid.length;
int n=grid[0].length;
if(grid[0][0]==1) return -1;
Queue<int[]> queue=new LinkedList<>();
queue.add(new int[]{0, 0, 1});
grid[0][0]=1;
int[][] dir={{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {-1, 1}, {0, -1}, {1, 1}};
while(queue.size()!=0){
int part[]=queue.remove();
if(part[0]==m-1 && part[1]==n-1) return part[2];
for(int d[]:dir){
int r=part[0]+d[0];
int c=part[1]+d[1];
if(r>=0 && c>=0 && r<m &&c<n &&grid[r][c]!=1){
queue.add(new int[]{r, c, part[2]+1});
grid[r][c]=1;
}
}
}
return -1;
}
}

[risingstar]

May be you know the answer very well. But honestly i couldn't understand your code from the point you started mentioning "level". I mean what do you mean by level is not at all clear.

[heisenberg]

Instead of giving grid[r][c] = 1 in the bottommost if statement, if I give grid[point[0]][point[1]] = 1 at the beginning of the inner while loop, it's giving TLE. Can you please explain why?