DAY 33 - Rotting Oranges

Hey everyone! Welcome back to another day of problem-solving. It's day 33, and I'm still going strong on my quest for consistency. Today, we have an interesting problem to tackle. But before we dive in, let's make sure we're all on the same page.

Incase you are unfamiliar with graphs I suggest reading the previous article. It also contains the links to valuable resources.

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.

Approach:

The objective is to determine the minimum number of minutes that must pass until no cell in the grid contains a fresh orange. If achieving this is impossible, we should return -1.

Now that we understand the problem, let's discuss our approach to solving it.

• To solve this problem, we can leverage a similar approach to the Breadth-First Search (BFS) technique we've encountered before.

• Our strategy involves identifying the rotten oranges as starting points and using the concept of adjacency to spread the rot to neighboring fresh oranges. We repeat this process until no more fresh oranges can be affected.

Algorithm:

• Obtain the dimensions of the grid, storing the number of rows in the variable m and the number of columns in the variable n.

• Define two arrays, rowTraverse and colTraverse, to represent the four possible directions: up, right, down, and left.

• Create a queue of pairs, where each pair represents the coordinates of an orange and its corresponding rotting time.

• Initialize a 2D vector, vis, of size m x n, to keep track of visited cells. Set all values to 0 initially.

• Iterate through the grid, checking for rotten oranges (represented by a value of 2). For each rotten orange found, enqueue its coordinates and set the corresponding vis value to 2.

• Initialize a variable, time, to track the maximum rotting time encountered so far.

• While the queue is not empty, perform the following steps:

• Dequeue an orange from the front of the queue, obtaining its row, column, and rotting time.

• Update time to the maximum value between time and the current rotting time.

• Explore the four adjacent cells (up, right, down, and left) of the dequeued orange:

• Calculate the coordinates of the adjacent cell using rowTraverse and colTraverse.

• Check if the adjacent cell is within the grid boundaries and is a fresh orange (represented by a value of 1) that has not been visited.

• If the conditions are met, enqueue the adjacent cell's coordinates and the current rotting time plus one into the queue. Set the corresponding vis value to 2.

• After the BFS traversal is complete, iterate through the grid again to check if any fresh oranges (with a value of 1) remain. If any are found, return -1 to indicate impossibility.

• Finally, return the value of time, which represents the minimum time required for all the oranges to rot.

Code:

int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int rowTraverse[] = {-1,0,1,0};
        int colTraverse[] = {0,1,0,-1};

        // stores row coloumn and time
        queue<pair<pair<int,int>,int>> q;
        vector<vector<int>> vis(m , vector<int>(n,0));

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 2){
                    q.push({{i,j},0});
                    vis[i][j] = 2;
                }
            }
        }
        int time = 0;
        while(!q.empty()){
            int row = q.front().first.first;
            int col = q.front().first.second;
            int t = q.front().second;
            time = max(time , t);
            q.pop();
            for(int i = 0; i < 4; i++){
            int nrow = row + rowTraverse[i];
            int ncol = col + colTraverse[i];
            if(nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && vis[nrow][ncol] != 2 && grid[nrow][ncol] == 1){
                q.push({{nrow,ncol},t+1});
                vis[nrow][ncol] = 2;
            }
        }
    }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(vis[i][j] !=2 && grid[i][j] == 1){
                    return -1;
                }
                }
            }
            return time;
    }

Complexity Analysis:

• Time Complexity: O(M*N)
• Space Complexity: O(M*N)

I hope this article helps you understand the problem and our approach to solving it. Feel free to provide feedback, and keep up the great work in your problem-solving journey!