# 994. Rotting Oranges

Question link is here.

# Question

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.

# Solution

Use BFS search, with start index at every initial rotten oranges in the queue. Check if there are still any fresh oranges left after the bfs.

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<Pair<Integer, Integer>> queue = new ArrayDeque<>();
        int total = 0;
        int res = 0;
        int height = grid.length;
        int width = grid[0].length;
        int[][] dirs = { {0,1}, {0, -1}, {-1, 0}, {1, 0}};
        for(int i = 0; i < height; i++) {
            for(int j = 0; j < width; j++) {
                if(grid[i][j] == 2)
                    queue.offer(new Pair(i, j));
                if(grid[i][j] == 1)
                    total += 1;
            }
        }
        if(total == 0)
            return 0;
        while(queue.size() != 0) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                Pair<Integer, Integer> p = queue.poll();
                int x = p.getKey();
                int y = p.getValue();
                for(int[] d:dirs) {
                    int nextX = x + d[0];
                    int nextY = y + d[1];
                    if(nextX >= 0 && nextY >= 0 && nextX < height && nextY < width && grid[nextX][nextY] == 1) {
                        queue.offer(new Pair(nextX, nextY));
                        grid[nextX][nextY] = 2;
                        total -= 1;
                    }
                }
            }
            res += 1;
        }
        if(total != 0)
            return -1;
        return res - 1;
    }
}

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        queue = []
        ans = 0
        total = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if(grid[i][j] == 1):
                    total += 1
                if(grid[i][j] == 2):
                    queue.append([i, j])
        dirs = [[-1,0],[1, 0], [0, -1], [0,1]]
        if total == 0:
            return 0
        while queue:
            print(queue)
            size = len(queue)
            for i in range(size):
                x, y = queue.pop(0)
                for row, col in dirs:
                    nextX = x + row
                    nextY = y + col
                    if(nextX >= 0 and nextY >= 0 and nextX < len(grid) and nextY < len(grid[0]) and grid[nextX][nextY] == 1):
                        queue.append([nextX, nextY])
                        grid[nextX][nextY] = 2
                        total -= 1
            ans += 1
        if total != 0:
            return -1
        return ans - 1

Time complexity: $O(n)$ where n is total number of cells in the grid.

Leetcode 994

Rotting Oranges

# 994. Rotting Oranges

# Question

# Solution