Leet Code 994. Rotting Oranges

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Isme BFS lagega,

Minute 0 - (0,0) rott hua

Minute 1 - (0,1), (1,0) rott hua, yeh dono child hai (0,0) ke

Queue kis type ki banege?

Method 1. pair type ki bnege, with x and y cordintes

Method 2.

Hum apne pairs ko transform kr denge

idx = i * m +j

i = current row number 

m = number of columns

j = current column number

x = idx /m

y = idx % m

public int orangesRotting(int[][] grid) {

    Queue<Integer> que = new ArrayDeque<>();
    int n = grid.length;
    int m = grid[0].length;
    int numberOfFreshOranges = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1)
                numberOfFreshOranges++;
            else if (grid[i][j] == 2)
                que.add(i * m + j);     // sab rotten oranges ko queue me daal diya
        }
    }

    // agr fresh oranges mile hi nhi, to humein 0 time lga
    if (numberOfFreshOranges == 0)
        return 0;

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

    while (!que.isEmpty()) {
        int size = que.size();

        while (size-- > 0) {
            // yeh nikala humne rotten orange
            // also, jo trasform hone ke lea aaenge
            int out = que.remove();

            // but aab out ke co-ordinates nikalne honge
            int x = out / m;
            int y = out % m;

            for (int[] dir : dirns) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
                    // queue me tabhi push krenge agr woh fresh orange hai
                    if (grid[newX][newY] == 1) {
                        grid[newX][newY] = 2;       // humne isko rott kr diya, aab yeh apne neighbour ko krega
                        que.add(newX * m + newY);
                        numberOfFreshOranges--;

                        if (numberOfFreshOranges == 0)
                            return level + 1;   // yha pr hum level nhi, level +1 return krenge
                        //  as queue me hum neighbour ko level 0 pr hi add krte hain
                        // but ideally woh level 1 pr rott hua hota hai

                    }
                }
            }

        }
        level++;
    }

    return -1;


}