Shortest Path in Binary Matrix | BFS | Dijkstra's | Google, Amazon | Leetcode-1091 | Live Code

This is the 28th Video on our Graphs Playlist.
In this video we will try to solve a very classic Graph Problem "Shortest Path in Binary Matrix " (Leetcode - 1091)

I am promising you, this problem will become easy once you are done with this video.
If you have been following my "Graph Concepts & Qns" playlist , then these Qns will become very easy. Find the Link for that below.

We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Shortest Path in Binary Matrix
Company Tags : Google, Amazon, Meta, Microsoft

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips
#interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook

[codestorywithMIK]

Hi guys, there is so much to learn from this video.
You will learn
1. Why BFS also works here.
2. Why Dijkstra's with min_heap as well as Queue work here.

You should know the WHY of everything in the problem.

I hope this video helps everyone.
Thank you all for watching my videos ❤❤❤

[animesh]

907. Sum of Subarray Minimums -->Make Solution on it with optimization.

[sidharthdhiman]

sir if possilbe can you make video on pacific Atlantic water flow

[JJ-tpdd]

Java Implementation:
BFS:
class Pair {
int first;
int second;

Pair(int _x, int _y) {
this.first = _x;
this.second = _y;
}
}

class Solution {

private int m;
private int n;

private boolean isSafe(int i, int j) {

if(i<0 || i>=m || j<0 || j>=n) return false;
return true;
}

public int grid) {

if(grid[0][0] == 1) return -1;

this.m = grid.length;
this.n = grid[0].length;
int [][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, 1}, {1, -1}, {-1, 1}};

Queue<Pair> q = new LinkedList<>();
q.offer(new Pair(0, 0));
grid[0][0] = 1;

int level = 0;

while(!q.isEmpty()) {
int N = q.size();
while(N-- > 0) {
Pair p = q.peek();
q.poll();
int x = p.first;
int y = p.second;

if(x==m-1 && y==n-1) return level+1;

for(int[] dir : directions) {
int x_ = x + dir[0];
int y_ = y + dir[1];

if(isSafe(x_, y_) && grid[x_][y_]==0) {
q.offer(new Pair(x_, y_));
grid[x_][y_] = 1;
}
}
}
level++;
}
return -1;
}
}

Dijkstra's :
class Triple {
int first;
int second;
int third;

Triple(int _w, int _x, int _y) {
this.first = _w;
this.second = _x;
this.third = _y;
}
}

class Solution {

private int m;
private int n;

private boolean isSafe(int i, int j) {

if(i<0 || i>=m || j<0 || j>=n) return false;
return true;
}

public int grid) {

if(grid[0][0] == 1) return -1;

this.m = grid.length;
this.n = grid[0].length;
int [][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, 1}, {1, -1}, {-1, 1}};

int[][] result = new int[m][n];
for(int[] res: result)
Arrays.fill(res, Integer.MAX_VALUE);

result[0][0] = 0;

PriorityQueue<Triple> pq = new PriorityQueue<Triple>((x, y) -> x.first - y.first);
pq.add(new Triple(0, 0, 0));

while(pq.size() != 0) {
int d = pq.peek().first;
int x = pq.peek().second;
int y = pq.peek().third;
pq.remove();

for(int[] dir : directions) {
int x_ = x + dir[0];
int y_ = y + dir[1];
int dist = 1;

if(isSafe(x_, y_) && grid[x_][y_]==0 && d+dist<result[x_][y_]) {
pq.add(new Triple(d+dist, x_, y_));
result[x_][y_] = d+dist;
}
}
}

if(result[m-1][n-1] == Integer.MAX_VALUE) return -1;
return result[m-1][n-1] + 1;

}
}

[xiaoshen]

Hello sir, plz wo codeforces wale E ques mein help kr dijiye (DSU wala). Koi bhi meri help nahi karta aur phir time pass ho jata Hai