class Solution { public int[][] updateMatrix(int[][] mat) { /* Q4 of graph playlist , add all zeroes to q and mark all 1 to -1 , fire bfs from all zeroes to find nearest 1 and update distance of 1 */ int m = mat.length , n = mat[0].length; LinkedList<pair> q = new LinkedList<>(); //adding all zeroes to the q for(int i =0 ; i < m ; i++){ for(int j = 0 ; j < n ;j++){ if(mat[i][j] == 0) q.addLast(new pair(i , j)); else mat[i][j] = -1; //marking the cell as unvisited } } //firing reverse bfs from zeroes to solve all 1's while(q.size()>0){ pair rem = q.removeFirst(); for(int i = 0 ;i < 4 ; i++){ int rowdash = rem.x + dir[i][0]; int coldash = rem.y + dir[i][1]; //if valid cell if(rowdash >= 0 && coldash >= 0 && rowdash < m && coldash < n && mat[rowdash][coldash] < 0){ //updating distance of the cell mat[rowdash][coldash] = mat[rem.x][rem.y] + 1; //adding it to q to solve further cells q.addLast(new pair(rowdash , coldash)); } } } return mat; } public int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}}; public class pair { int x , y; pair(int x , int y){ this.x = x; this.y = y; } } }