Rotting Oranges

Recently, I came across this very beautiful problem which is also a very good use case of graph breadth first search algorithm.

Problem Statement

Suppose we are given a grid of 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. We have to return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Visualization

Let’s visualize this problem first. Suppose we have a tray full of oranges. In the tray some oranges are rotten, some are fresh, and oranges may or may not have any space between them.

Rotten — brown colored and Fresh — orange colored

In the above diagram, first orange in top left is rotten, so it can rot all it’s adjacent fresh oranges in one go. Let’s see how the rotting process will take place.

All the rotten oranges will rot their adjacent fresh oranges in next minute

All the newly rotten oranges will rot their adjacent fresh oranges in the next minute

No more rotting is possible as all the rotten oranges have already rot their neighboring fresh oranges. So, after the process is done, one fresh orange is left with us which can’t be rotten. So, in this case, it’s impossible to rot all the fresh oranges.

Strategy

1. Find all the oranges that are initially rotten.
2. In the next one minute, these rotten oranges will rot the neighboring fresh oranges. And this process will continue till all the rotten oranges have rot their adjacent fresh oranges.

We can think of it in a level by level manner. All the initial rotten oranges are at level 0. Then the adjacent fresh oranges to these rotten oranges are in level 1 and the next in level 2 and so on. Therefore, the time required to rot all the possible fresh oranges will be equal to the number of levels.

But, there is one more possibility. It is possible that there are no fresh oranges in the beginning. In that case time required will be zero.

Code analysis

• Initialize a queue for breadth first search.
• Iterate over the entire grid and add all the rotten oranges in the queue and also keep counting the number of fresh oranges.
• If the number of fresh oranges is zero then we can directly return zero.
• Otherwise, traverse the queue in level order fashion and add all the adjacent fresh oranges in the queue and decrement the count of fresh oranges by 1 each time. When we add a fresh orange in the queue, we mark it as rotten so that it is not added multiple times.
• If after one complete traversal of a level, the queue is not empty, then increase the minutes by one.
• Repeat this process until we have no more rotten oranges.
• If the number of fresh oranges after the entire process is still not zero, then return -1 indicating that it’s impossible to rot all the oranges.
• Else return the time required to rot all the oranges.

Code

private static int[] xdir = new int[]{-1, 1, 0, 0};
private static int[] ydir = new int[]{0, 0, -1, 1};
private boolean isValid(int i, int j, int rows, int cols){
    return i>=0 && j>=0 && i<rows && j<cols;
}
public int orangesRotting(int[][] grid) {
    if(grid == null || grid.length == 0) return 0;
    int rows = grid.length;
    int cols = grid[0].length;
    int time = 0;
    int freshOrangeCount = 0;

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

    for(int i=0; i<rows; i++){
        for(int j=0; j<cols; j++){
            if(grid[i][j] == 2){
                queue.add(i*cols+j); //inserting row and col index in 1D form so as to avoid packing and unpacking
            } else if(grid[i][j]==1){
                freshOrangeCount++;
            }
        }
    }

    if(freshOrangeCount == 0) return 0;

    while(!queue.isEmpty()){
        int size = queue.size();
        while(size-- > 0){
            int top = queue.poll();
            int r = top/cols;
            int c = top%cols;

            for(int i=0; i<4; i++){
                int newR = r+xdir[i];
                int newC = c+ydir[i];

                if(isValid(newR, newC, rows, cols) && grid[newR][newC]==1){
                    grid[newR][newC] = 2;
                    queue.add(newR*cols + newC);
                    freshOrangeCount--;
                }
            }
        }

        if(queue.size() > 0){
            ++time;
        }
    }

    return freshOrangeCount>0?-1:time;
}

Complexity Analysis

Time complexity = O(n*m) for first traversal of the grid to find all the rotten and fresh oranges + O(n*m) for queue traversal if there is only one fresh orange and that too when the last orange is fresh.

Space complexity = O(n*m) extra space for queue in the worst case when all the oranges are rotten.

n — number of rows
m– number of cols

Guys I really hope that you find this article valuable! If still, you have any queries, you can surely discuss them in the comment section below.

Thanks a lot for devoting your time to this blog. Your claps motivate me to write more such blogs!