Rotting Oranges

Leetcode 994. Rotting Oranges

Problem

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

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.

Source: Leetcode 994. Rotting Oranges

Solution

This problem can be solved using Breadth First Search (BFS) algorithm, which is an algorithm originally invented to “for searching a tree data structure for a node that satisfies a given property.“ (BFS – wikipedia)

How BFS Works

Let’s say we have a graph data structure where nodes are connected by edges. We also have a queue to store node values. We want to find the distance from a start node to an end node. Here, each node has same amount of distance, say 1 unit, from its adjacent node.

BFS takes the start node and pushes into the queue and assigns current_distance = 0. This is the distance from the current node (which is just pushed into the queue) from itself. This is the first step.

Then it runs a loop until the queue is empty or it reaches to the end node. Inside that loop, it pops node from the queue, then take adjacent elements of that (recently popped) node into the queue and update distance of adjacent nodes as current_distance + 1. This loop runs until the queue is empty or the algorithm finds the end node.

As we can visualize, BFS works like a wave or a layered approach. For a single node, it explores all nodes adjacent to it. Before explore all adjacent nodes, it doesn’t go in any depth.

However, let’s see this algorithm in action to solve this problem. It’s better to understand visually!

BFS in Rotting Oranges

Let’s say we have a grid as below. We have some cells with 0 value having no oranges, with 2 value having rotting oranges and 1 value having good oranges.

We will have to find how many minutes will elapse until all oranges are rotted, right?

In other words, we need to find how many layers are away from a rotting orange to cover all the good oranges!

For example, the first rotting orange is 2 with layer 0 and coordinate {0, 0}. In the next layer, we have 1 with layer 1 and coordinate {0, 1}. Then we have 1 with layer 2 and coordinate {1, 1} and so on.

See we are just exploring the adjacent nodes of a node and assigning layer + 1 to the newly explored node, right?

Let’s get back to the solution again.

We have a queue which will store a data structure structure for a node like { node_coordinate_x, node_coordinate_y, distance}.

At first we count how many fresh oranges (i.e. nodes with 1) we have and save it in a variable like total_fresh = 6.

Then we find all the rotting oranges push them in our queue. Remember, while pushing we are adding their coordinates (in this case, i and j values) and their initial distance (in other words, layer number). For the first rotting orange, it is {0, 0, 0}.

Now we will loop through the queue, pop the first node from queue and explore each adjacent 1 nodes (of the popped node) one after another. There are two adjacent nodes which are {1, 0} and {0, 1}. Since {1, 0} do not have any fresh orange, we will not take that node.

So, there is only one adjacent 1 node (i.e. node with fresh orange) of node {0, 0} which is node {0, 1}.

We push the explored node to the queue and update its distance to be 1 (distance = distance of popped node + 1).

Since we explored a fresh node (i.e. node with value 1) and made it rotten, our total_fresh is now reduced to 1!

Now we will explore the adjacent nodes of node {0, 1}. In the same way, we find node {1, 1} should be added in the queue. We update distance of this node and update total_fresh as below image.

Now we will explore the adjacent nodes of node {1, 1}. In the same way, we find node {1, 2} and {2,1} should be added in the queue. Here, do we need to maintain any order when we find more than one valid adjacent node? No, not necessary at least for this problem.

We update distances of these new nodes and update total_fresh as below image. Since we found two fresh oranges in these nodes, we reduced total_fresh by 2.

We now will explore the adjacent nodes of node {1, 2} (it could be node {2, 1} also, order doesn’t matter). In the same way, we find node {2, 2} should be added in the queue. We update distance of this node and update total_fresh as below image.

Then we will explore the adjacent nodes of node {2, 1}. But wait, there was only one valid adjacent node which is {2, 2}. But that one is already explored! So, we won’t do anything with it and continue to the loop.

Now we will explore the adjacent nodes of node {2, 2}. We find node {2, 3} should be added in the queue. We update distance of this node and update total_fresh as below image.

We see, total_fresh has become 0 when we reached at node {2, 3}. So, the distance when we reached node {2, 3} should be the time required to make all oranges rotten! So, we simply return this answer :).

Code

C++

class Solution {
public:
    int countFresh(vector<vector<int>>& grid){
        int total_fresh = 0;
        for(int i = 0; i < grid.size(); i++)
            for(int j = 0; j < grid[i].size(); j++)
                if(grid[i][j] == 1) total_fresh+= 1;
        return total_fresh;
    }
    
    int orangesRotting(vector<vector<int>>& grid) {
        int total_fresh = countFresh(grid);
        if(total_fresh == 0)
            return 0;
        
        queue<vector<int>> q;
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(grid[i][j] == 2) {
                    q.push({i, j, 0});
                    visited[i][j] = true;
                }
            }
        }
        
        vector<vector<int>> dir = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        
        while(!q.empty()){
            
            vector<int> parent = q.front(); q.pop();
            int r = parent[0];
            int c = parent[1];
            int dist = parent[2];
            
            for(int i = 0; i < 4; i++){
                int new_r = r + dir[i][0];
                int new_c = c + dir[i][1];
                
                if(0 <= new_r && new_r < grid.size() && 0 <= new_c && new_c < grid[0].size()){
                    if(grid[new_r][new_c] == 1 && !visited[new_r][new_c]){
                        visited[new_r][new_c] = true;
                        q.push({new_r, new_c, dist + 1});
                        total_fresh -= 1;
                        if(total_fresh == 0) return dist + 1;
                    }
                }
            }
        }
        
        return -1;
    }
};

Complexity Analysis

Since we have to explore all the nodes, in worst case, the time and space complexity will be the total number of cells in the matrix.

Conclusion

Hope you enjoyed the solution, though it was an easy problem and a simple version of BFS algorithm. 🙂 

Did we make it too complex explaining this? 🙁 Not sure!

Can you write down about it?

Also, you can let us know what difficulty you are facing solving leetcode problems in general. If you love our blog or hate it, please shout out!

Happy coding! 🙂