class Solution {
public int maxDistance(int[][] grid) {
/* Q-6 of graph playlist , we make a pair class with row , col , distance , first
add all 1s to the q with distance 0 , fire bfs , encountering a 0 we change it to 1
and make its distance + 1
we keep a max variable also while we fire bfs and store max distance along the way
*/
int m = grid.length , n = grid[0].length ;
LinkedList<pair> q = new LinkedList<>();
//adding all 1s to q
int water = 0 , land = 0;
for(int i = 0 ;i < m ;i++){
for(int j = 0 ; j < n ;j++){
if(grid[i][j] == 1){
land ++;
q.addLast(new pair(i, j , 0));
}
else
water++;
}
}
//edge case
if(water == 0 || land == 0) return -1;
int max = -1;
//firing bfs
while(q.size() > 0){
pair rem = q.removeFirst();
int row = rem.x ; int col = rem.y ; int dist = rem.dist;
max = Math.max(dist , max);
for(int i =0 ;i < 4 ; i++){
int rowdash = row + dir[i][0];
int coldash = col + dir[i][1];
//if valid water cell change it to land cell and make its dist + 1
if(rowdash >=0 && coldash >=0 && rowdash < m && coldash < n &&
grid[rowdash][coldash] == 0){
grid[rowdash][coldash] = 1;
q.add(new pair(rowdash , coldash , dist + 1));
}
}
}
return max;
}
public int dir [][] = {{0,1},{1,0},{-1,0},{0,-1}};
public class pair{
int x , y , dist;
pair(int x , int y , int dist){
this.x = x; this.y = y ; this.dist = dist;
}
}
}
Comments