Leetcode Top 100 Liked Series #30 — Rotting Oranges

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

2. Initial Solution(Passed, but inefficient)

My first approach is:

1. Find all locations of rotten oranges.
2. At the same time, count number of fresh oranges
3. If there is no fresh orange, we don’t need to propagate. so return 0
4. while queue is not empty(there are the locations of rotten orange inside queue), push available locations among 4-directions into new queues if it is not visited and the value is one. After then, we change previous queue with new queue.
5. Iterate step4.

class Solution {
    int visited[11][11] = {0};

public:
    int orangesRotting(vector<vector<int>>& grid) {
        bool noway = false;
        int freshes = 0;
        deque<vector<int>> q;
    
//Find all locations of rotten oranges & At the same time, count number of fresh oranges
        for(int i=0; i < grid.size(); i++) {
            for(int j=0; j < grid[0].size(); j++) {
                if(grid[i][j] == 2) {
                    vector<int> temp = {i, j};
                    q.push_back(temp);
                }
                else if(grid[i][j] == 1){
                    freshes += 1;
                }
            }
        }
//If there is no fresh orange, we don't need to propagate. so return 0
        if(freshes == 0) return 0;
        

        int minutes = 0;
        while(!q.empty())
        {
            minutes += 1;
            deque<vector<int>> dt;
            while(!q.empty())
            {
                auto temp = q.front();
                q.pop_front();
                int row = temp[0];
                int col = temp[1];
                visited[row][col] = 1;

                if(row - 1 >= 0) {
                    if(grid[row-1][col] == 1 && visited[row-1][col] == 0) {
                        vector<int> coor = {row-1, col};
                        visited[row-1][col] = 1;
                        freshes -= 1;
                        dt.push_back(coor);
                    } 
                }
                if(col -1 >= 0) {
                    if(grid[row][col-1] == 1 && visited[row][col-1] == 0) {
                        vector<int> coor = {row, col-1};
                        visited[row][col-1] = 1;
                        freshes -= 1;
                        dt.push_back(coor);
                    } 
                }
                if(row + 1 < grid.size()) {
                    if(grid[row+1][col] == 1 && visited[row+1][col] == 0) {
                        vector<int> coor = {row+1, col};
                        visited[row+1][col] = 1;
                        freshes -= 1;
                        dt.push_back(coor);
                    } 
                }
                if(col + 1 < grid[0].size()){
                    if(grid[row][col+1] == 1 && visited[row][col+1] == 0) {
                        vector<int> coor = {row, col+1};
                        visited[row][col+1] = 1;
                        freshes -= 1;
                        dt.push_back(coor);
                    } 
                }

            }
            q = dt;
        }

        return (freshes > 0) ? -1 : minutes-1;
    }   
};

Let’s see a result.

Holly molly, The performance is horrible.

This is one of efficient solutions from leetcode

class Solution {
    int visited[11][11] = {0};

public:
    int orangesRotting(vector<vector<int>>& grid) {
        int dir[5] = {-1, 0, 1, 0 ,-1};
        int m = grid.size();
        int n = grid[0].size();

        queue<pair<int, int>> q; // data structure optimized: vector -> pair;

        //below steps are same with my initial solution
        int fresh=0; //To keep track of all fresh oranges left
        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]==1)
                    fresh++;
            }
        int ans=-1;

         while(!q.empty())
        {
            int sz=q.size();
            while(sz--)
            {
                pair<int,int> p=q.front();
                q.pop();
                for(int i=0;i<4;i++)
                {
                    int r=p.first+dir[i];
                    int c=p.second+dir[i+1];
                    if(r>=0 && r<m && c>=0 && c<n &&grid[r][c]==1)
                    {
                        grid[r][c]=2;
                        q.push({r,c});
                        fresh--; // decrement by 1 foreach fresh orange that now is rotten
                    }
                    
                }
            }
            ans++; //incremented after each minute passes
        }

        
        if(fresh>0) return -1; 
        if(ans==-1) return 0; 
        return ans;
    }   
};

The whole approach is not that different. but the key difference is to use proper data structure and reduce condition blocks by using direction.

From this problem, I realized that solid understanding about BFS is important.

Reference

Problem Source : https://leetcode.com/problems/rotting-oranges/description/