Rotting Oranges

---

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:

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.

---

Try this Problem on your own or check similar problems:

1. Detonate the Maximum Bombs
2. Escape the Spreading Fire

Solution:

Java

class Solution {
  int[][] directions  = new int[][] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }};
  public int orangesRotting(int[][] grid) {
      int m = grid.length, n = grid[0].length;
      Queue<int[]> q = new LinkedList<>();
      int time = 0, numberOfOranges = 0;

      for(int i = 0; i < m; ++i){
        for(int j = 0; j < n; ++j){
          if(grid[i][j] == 2) q.add(new int[]{i, j});
          if(grid[i][j] != 0) ++numberOfOranges;
        }
      }

      if(numberOfOranges == 0) return 0;

      while(!q.isEmpty()){
        int size = q.size();
        while(size-- > 0){
          int[] current = q.poll();
          --numberOfOranges;
          for(int[] d: directions){
            int newRow = current[0] + d[0];
            int newCol = current[1] + d[1];
            if(newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || grid[newRow][newCol] != 1) continue;
            grid[newRow][newCol] = 2;
            q.add(new int[]{newRow, newCol});
          }
        }
        ++time;
      }

      return numberOfOranges == 0 ? time - 1 : -1;
  }
}

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
  const directions = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
  ];
  const m = grid.length;
  const n = grid[0].length;
  const q = [];
  let time = 0;
  let numberOfOranges = 0;

  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (grid[i][j] === 2) {
        q.push([i, j]);
      }
      if (grid[i][j] !== 0) {
        numberOfOranges++;
      }
    }
  }

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

  while (q.length > 0) {
    const size = q.length;
    for (let i = 0; i < size; ++i) {
      const current = q.shift();
      numberOfOranges--;
      for (const [dx, dy] of directions) {
        const newRow = current[0] + dx;
        const newCol = current[1] + dy;
        if (
          newRow < 0 ||
          newRow >= m ||
          newCol < 0 ||
          newCol >= n ||
          grid[newRow][newCol] !== 1
        ) {
          continue;
        }
        grid[newRow][newCol] = 2;
        q.push([newRow, newCol]);
      }
    }
    time++;
  }

  return numberOfOranges === 0 ? time - 1 : -1;
};

Python

class Solution:
    directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = deque()
        time = 0
        numberOfOranges = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append([i, j])
                if grid[i][j] != 0:
                    numberOfOranges += 1

        if numberOfOranges == 0:
            return 0

        while q:
            size = len(q)
            for _ in range(size):
                current = q.popleft()
                numberOfOranges -= 1
                for d in self.directions:
                    newRow = current[0] + d[0]
                    newCol = current[1] + d[1]
                    if newRow < 0 or newRow >= m or newCol < 0 or newCol >= n or grid[newRow][newCol] != 1:
                        continue
                    grid[newRow][newCol] = 2
                    q.append([newRow, newCol])
            time += 1

        return time - 1 if numberOfOranges == 0 else -1

C++

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        std::vector<std::vector<int>> directions{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        int m = grid.size();
        int n = grid[0].size();
        std::queue<std::pair<int, int>> q;
        int time = 0;
        int numberOfOranges = 0;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 2) {
                    q.push({i, j});
                }
                if (grid[i][j] != 0) {
                    numberOfOranges++;
                }
            }
        }

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

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto current = q.front();
                q.pop();
                numberOfOranges--;
                for (const auto& d : directions) {
                    int newRow = current.first + d[0];
                    int newCol = current.second + d[1];
                    if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || grid[newRow][newCol] != 1) {
                        continue;
                    }
                    grid[newRow][newCol] = 2;
                    q.push({newRow, newCol});
                }
            }
            time++;
        }

        return numberOfOranges == 0 ? time - 1 : -1;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(mn)
• Space Complexity: O(mn)

---

Explanation:

We implement the same BFS logic as we have seen in 01 Matrix of having first the initial candidates (already rotten oranges in this problem) and then searching for the next level of candidates which are neighbors of rotten oranges. We do that as long as we have a non-empty queue. We mark each visited neighbor by setting its value to 2 (rotten orange). Initially we also count the total number of oranges and then in our queue traversal we decrement that so we can use that information to see if we have visited all the oranges (or if it's not possible to visit them all). For each level we increase the time, and we return time - 1 as our final result since we don't count the first set of candidates (they're already rotten in the "0 minute"), otherwise if we couldn't reach all oranges, we return -1. The time and space complexity are proportional to the size of the grid O(mn).