Rotting Oranges

Problem

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

• 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.

Solution

BFS

As the rot spreads by 1 unit in all directions at the same time, we use Breadth-First Search (BFS). We start by adding all the rotten oranges' row and column pairs to the queue because they spread the rot to nearby neighbors simultaneously. Each time we process the queue, it represents an increase of 1 unit of time. This means that when we add an orange to the queue, it becomes rotten.

Note: We start the timer at -1 because when we check the neighbors of the last rotten orange in the queue, an extra 1 is added even though it is already rotten. Therefore, we need to subtract 1.

Analogy with a tree: The children of a node are (i-1, j), (i+1, j), (i, j-1), and (i, j+1), which are the children of the node (i, j). We also need to check if these nodes have been visited, if they have valid indices, and if they represent a fresh mango.

Time - O(nxm)

Space - O(nxm)

class Solution {

    class Pair{
        int i;
        int j;
        Pair(int i, int j){
            this.i = i;
            this.j = j;
        }
    }

    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] visited = new int[m][n];

        Queue<Pair> queue = new ArrayDeque<>();

        initializeQueue(queue, visited, grid);

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

            for(int k=0; k<size; k++){
                Pair pair = queue.poll();
                int i = pair.i;
                int j = pair.j;

                if(isValid(i-1, j, visited, grid)) {
                    queue.add(new Pair(i-1, j));
                    visited[i-1][j] = 1;
                }
                if(isValid(i+1, j, visited, grid)){
                    queue.add(new Pair(i+1, j));
                    visited[i+1][j] = 1;
                }
                if(isValid(i, j-1, visited, grid)){
                    queue.add(new Pair(i, j-1));
                    visited[i][j-1] = 1;
                }
                if(isValid(i, j+1, visited, grid)){
                    queue.add(new Pair(i, j+1));
                    visited[i][j+1] = 1;
                }
            }
            timer += 1;
        }

        if(timer==-1) timer=0;
        return checkAllRoten(grid, visited) ? timer: -1;
    }

    private void initializeQueue(Queue<Pair> queue, int[][] visited, int[][] grid){
        int m = visited.length;
        int n = visited[0].length;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 2){
                    queue.add(new Pair(i, j));
                    visited[i][j] = 1;
                }
            }
        }
    }

    private boolean isValid(int i, int j, int[][] visited, int[][] grid){
        int m = visited.length;
        int n = visited[0].length;

        if(i<0 || i>=m) return false;
        if(j<0 || j>=n) return false;
        if(visited[i][j]==1) return false;
        if(grid[i][j]!=1) return false;

        return true;
    }

    private boolean checkAllRoten(int[][] grid, int[][] visited){
        int m = visited.length;
        int n = visited[0].length;

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 1 && visited[i][j] == 0){
                    return false;
                }
            }
        }
        return true;
    }
}

Optimize Version

We can simplify the process by counting the fresh mangoes while initializing the queue. At the end, we just need to check if we have rotted the same number of fresh mangoes. If we have, then all the mangoes are rotten.

class Solution {

    class Pair{
        int i;
        int j;
        Pair(int i, int j){
            this.i = i;
            this.j = j;
        }
    }

    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] visited = new int[m][n];

        Queue<Pair> queue = new ArrayDeque<>();

        int freshOranges = initializeQueue(queue, visited, grid);

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

            for(int k=0; k<size; k++){
                Pair pair = queue.poll();
                int i = pair.i;
                int j = pair.j;

                if(isValid(i-1, j, visited, grid)) {
                    queue.add(new Pair(i-1, j));
                    visited[i-1][j] = 1;
                    freshOranges-=1;
                }
                if(isValid(i+1, j, visited, grid)){
                    queue.add(new Pair(i+1, j));
                    visited[i+1][j] = 1;
                    freshOranges-=1;
                }
                if(isValid(i, j-1, visited, grid)){
                    queue.add(new Pair(i, j-1));
                    visited[i][j-1] = 1;
                    freshOranges-=1;
                }
                if(isValid(i, j+1, visited, grid)){
                    queue.add(new Pair(i, j+1));
                    visited[i][j+1] = 1;
                    freshOranges-=1;
                }
            }
            timer += 1;
        }

        if(timer==-1) timer=0;
        return freshOranges==0 ? timer: -1;
    }

    private int initializeQueue(Queue<Pair> queue, int[][] visited, int[][] grid){
        int m = visited.length;
        int n = visited[0].length;
        int freshOranges = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 2){
                    queue.add(new Pair(i, j));
                    visited[i][j] = 1;
                }
                else if(grid[i][j] == 1){
                    freshOranges += 1;
                }
            }
        }
        return freshOranges;
    }

    private boolean isValid(int i, int j, int[][] visited, int[][] grid){
        int m = visited.length;
        int n = visited[0].length;

        if(i<0 || i>=m) return false;
        if(j<0 || j>=n) return false;
        if(visited[i][j]==1) return false;

        if(grid[i][j]!=1) return false;

        return true;
    }

}