LeetCode 994 - Rotting Oranges

https://leetcode.com/problems/rotting-oranges/

In a given grid, each cell can have one of three values:

• the value 0 representing an empty cell;
• the value 1 representing a fresh orange;
• the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1 instead.

1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. grid[i][j] is only 0, 1, or 2

https://leetcode.com/problems/rotting-oranges/discuss/238681/Java-Clean-BFS-Solution-with-comments

    public int orangesRotting(int[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int count_fresh = 0;
        //Put the position of all rotten oranges in queue
        //count the number of fresh oranges
        for(int i = 0 ; i < rows ; i++) {
            for(int j = 0 ; j < cols ; j++) {
                if(grid[i][j] == 2) {
                    queue.offer(new int[]{i , j});
                }
                else if(grid[i][j] == 1) {
                    count_fresh++;
                }
            }
        }
        //if count of fresh oranges is zero --> return 0 
        if(count_fresh == 0) return 0;
        int count = 0;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        //bfs starting from initially rotten oranges
        while(!queue.isEmpty()) {
            ++count;
            int size = queue.size();
            for(int i = 0 ; i < size ; i++) {
                int[] point = queue.poll();
                for(int dir[] : dirs) {
                    int x = point[0] + dir[0];
                    int y = point[1] + dir[1];
                    //if x or y is out of bound
                    //or the orange at (x , y) is already rotten
                    //or the cell at (x , y) is empty
                        //we do nothing
                    if(x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] == 0 || grid[x][y] == 2) continue;
                    //mark the orange at (x , y) as rotten
                    grid[x][y] = 2;
                    //put the new rotten orange at (x , y) in queue
                    queue.offer(new int[]{x , y});
                    //decrease the count of fresh oranges by 1
                    count_fresh--;
                }
            }
        }
        return count_fresh == 0 ? count-1 : -1;
    }

https://leetcode.com/articles/rotting-oranges/

  int[] dr = new int[] { -1, 0, 1, 0 };

  int[] dc = new int[] { 0, -1, 0, 1 };

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

    int R = grid.length, C = grid[0].length;

    // queue : all starting cells with rotten oranges

    Queue<Integer> queue = new ArrayDeque();

    Map<Integer, Integer> depth = new HashMap();

    for (int r = 0; r < R; ++r)

      for (int c = 0; c < C; ++c)

        if (grid[r][c] == 2) {

          int code = r * C + c;

          queue.add(code);

          depth.put(code, 0);

        }

    int ans = 0;

    while (!queue.isEmpty()) {

      int code = queue.remove();

      int r = code / C, c = code % C;

      for (int k = 0; k < 4; ++k) {

        int nr = r + dr[k];

        int nc = c + dc[k];

        if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {

          grid[nr][nc] = 2;

          int ncode = nr * C + nc;

          queue.add(ncode);

          depth.put(ncode, depth.get(code) + 1);

          ans = depth.get(ncode);

        }

      }

    }

    for (int[] row : grid)

      for (int v : row)

        if (v == 1)

          return -1;

    return ans;

  }

X. https://leetcode.com/problems/rotting-oranges/discuss/238579/C%2B%2BJava-with-picture-BFS

private int rot(int[][] g, int i, int j, int d) {
  if (i < 0 || j < 0 || i >= g.length || j >= g[i].length || g[i][j] != 1) return 0;
  g[i][j] = d + 3;
  return 1;
}
public int orangesRotting(int[][] g) {
  int fresh = 0, d = 0;
  for (int i = 0; i < g.length; ++i)
    for (int j = 0; j < g[i].length; ++j)
      if (g[i][j] == 1) ++fresh;
  for (int old_fresh = fresh; fresh > 0; ++d, old_fresh = fresh) {
    for (int i = 0; i < g.length; ++i)
      for (int j = 0; j < g[i].length; ++j)
        if (g[i][j] == d + 2)
          fresh -= rot(g, i + 1, j, d) + rot(g, i - 1, j, d) + rot(g, i, j + 1, d) + rot(g, i, j - 1, d);
    if (fresh == old_fresh) return -1;
  }
  return d;
}

Complexity Analysis

Time: O(h * w * (h + w)), where h and w are the dimension of the grid. We are scanning h + w times (maximum distance between two cells) through all grid cells.
Memory: O(1).