Skip to content

994. Rotting Oranges

You are given an m x n grid where each cell can have one of three values:

  • 0 representing an empty cell,
  • 1 representing a fresh orange, or
  • 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent 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.

Example 1:

img

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

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2.

Solution:

class Solution {
    public int orangesRotting(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        int[][] visited =  grid;

        Deque<int[]> queue = new ArrayDeque<>();

        int countFreshOrange = 0;

        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                if (visited[i][j] == 2){
                    queue.offerLast(new int[]{i, j});
                }

                if (visited[i][j] == 1){
                    countFreshOrange++;
                }
            }
        }

        if (countFreshOrange == 0){
            return 0;
        }

        if (queue.isEmpty()){
            return -1;
        }

        int minutes = -1;


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

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

            for (int i = 0; i < size; i++){
                int[] cur = queue.pollFirst();
                int x = cur[0];
                int y = cur[1];

                for (int[] dir : dirs){
                    int nX = x + dir[0];
                    int nY = y + dir[1];

                    if (nX >= 0 && nX < row && nY >= 0 && nY < col && visited[nX][nY] == 1){
                        visited[nX][nY] = 2;
                        countFreshOrange--;
                        queue.offerLast(new int[]{nX, nY});
                    }
                }

            }
            minutes++;

        }


        if (countFreshOrange == 0){
            return minutes;
        }

        return -1;

    }
}

// TC: O(n^2)
// SC: O(n^2)