994. Rotting Oranges

• Link: https://leetcode.com/problems/rotting-oranges/description/

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|2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1|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.

Approach 1: Optimal

Intuition

• Multisource BFS
• Directions array

Algorithm

1. Declare and initialize variables integers
   1. rows
   2. cols
   3. time
   4. freshOranges
2. Declare and intialize queue queue<pair<pair<int,int>int>> q indicating {{row, col}, time}
3. Traverse through the grid:
   1. If cell is 1 then freshOranges++
   2. If cell is 2 then push it to the queue with time as 0
4. Declare & initialize a directions array
5. BFS loop till the queue is not empty
   1. Get row, col & time in r, c & t from q.front()
   2. Pop the queue
   3. Update the time = max(time, t)
   4. Loop over the directions array
      1. nr = r + direction.first
      2. nc = c + direction.second
      3. if nr & nc are within bounds and has 1
         1. We update the cell to 2
         2. Push the position in the queue
         3. Decrement freshOranges
6. If freshOranges == 0, return time
7. else return -1

Code

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        int freshOranges = 0, time = 0;

        queue<pair<pair<int, int>, int>> q;

        for (int i = 0 ; i < rows ; i++) {
            for (int j = 0 ; j < cols ; j++) {
                if (grid[i][j] == 1) {
                    freshOranges++;
                } else if (grid[i][j] == 2) {
                    q.push({{i, j}, 0});
                }    
            }
        }

        vector<pair<int, int>> directions = {
            {-1, 0},
            {1, 0}, 
            {0, -1},
            {0, 1}
        };
        
        while (!q.empty()) {
            int r = q.front().first.first;
            int c = q.front().first.second;
            int t = q.front().second;
            q.pop();
            
            time = max(time, t);
            
            for (auto direction: directions) {
                int nr = r + direction.first;
                int nc = c + direction.second;
                
                if (nr >= 0 && nr < rows
                    && nc >= 0 && nc < cols
                    && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        q.push({{nr, nc}, t+1});
                        freshOranges--;
                }
            }
        }

        return freshOranges ? -1 : time;
    }
};

Complexity Analysis

• Time Complexity: $O(n\ast m)$
• Space Complexity: $O(n\ast m)$
• n -> rows, m -> cols