Leet Code 542. 01 Matrix

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Find: Har element ka uske nearest 0 se distance kitna hai

BFS lagaenge

add -> mark -> remove -> add nbr

    --> isme hum push hone se pehle hi visited me mark kr dete hain. Hence, cycle detect nhi ho paege

PREVIOS: add -> remove -> mark -> add nbr    

    --> we detected cycle, jo humne pop kiya hai kya woh pehle se visited hai

ADJACENT -> jo edge share krte hain

package pep.Day42;

import java.util.ArrayDeque;
import java.util.Queue;

public class LeetCode_01_Matrix {
    public static void main(String[] args) {
        int[][] matrix = {{0, 0, 0}, {0, 1, 0}, {1, 1, 1}};
        System.out.println(updateMatrix(matrix));

    }

    public static int[][] updateMatrix(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        boolean[][] visited = new boolean[n][m];

        Queue<Integer> que = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    visited[i][j] = true;
                    que.add(i * m + j);
                }
            }
        }

        while (!que.isEmpty()) {
            int out = que.remove();
            int i = out / m;
            int j = out % m;

            int[][] dirns = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

            for (int[] dir : dirns) {
                int x = dir[0] + i;
                int y = dir[1] + j;
                // 1. ans figureout krna hai
                // 2. jinko add krenge unko visited mark krna hai, i.e
                //ans[new] = ans[prev] +1
                if (x < 0 || y < 0 || x >= n || y >= m || visited[x][y])
                    continue;

                visited[x][y] = true;
                matrix[x][y] = matrix[i][j] + 1;
                // also, jiska nearest nikaal chuke hain, usko add kr denge
                // queue me, take auron ke lea answer dega woh
                que.add(x * m + y);
            }
        }
        return matrix;
    }
}