Rotting Fruit

Problem

You are given a 2-D matrix grid. Each cell can have one of three possible values:

• 0 representing an empty cell
• 1 representing a fresh fruit
• 2 representing a rotten fruit

Every minute, if a fresh fruit is horizontally or vertically adjacent to a rotten fruit, then the fresh fruit also becomes rotten.

Return the minimum number of minutes that must elapse until there are zero fresh fruits remaining. If this state is impossible within the grid, return -1.

Examples

Example 1:

Input: grid = [[1,1,0],[0,1,1],[0,1,2]]

Output: 4

Example 2:

Input: grid = [[1,0,1],[0,2,0],[1,0,1]]

Output: -1

Constraints

• 1 <= grid.length, grid[i].length <= 10

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the given grid.

Solution

Use BFS, but we need to be careful because we need to simulate an outer loop over all minutes. We do this by tracking the open size. We decrement every loop, and at the end of the loop if we hit 0, we set the size back. We need to only do this if empty is non-empty, otherwise we tick over at the last iteration.

class Solution {
    inline static std::array<std::pair<int, int>, 4> OFFSETS = {{
        {1, 0}, {-1, 0}, {0, 1}, {0, -1}
    }};
 
public:
    int orangesRotting(vector<vector<int>>& grid) {
        const int EMPTY = 0;
        const int FRESH = 1;
        const int ROTTEN = 2;
        const int ROWS = grid.size();
        const int COLS = grid[0].size();
 
        // Look for rotten fruit, BFS over rotten
        std::queue<std::pair<int, int>> open;
        int fresh_counter = 0;
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                if (grid[r][c] == ROTTEN) {
                    open.emplace(r, c);
                } else if (grid[r][c] == FRESH) {
                    ++fresh_counter;
                }
            }
        }
 
        // Important: if there are no fresh fruit, answer is 0,
        // even if there are also no rotten fruit.
        if (fresh_counter == 0) { return 0; }
 
        // Fresh fruit exist, but no rotten fruit to start infection.
        if (open.empty()) { return -1; }
 
        int minute = 0;
        int open_size = open.size();
        while (!open.empty()) { 
            auto [row, col] = open.front();
            open.pop();
            --open_size;
            // Infect neighbors
            for (const auto &[dr, dc] : OFFSETS) {
                auto r = row + dr;
                auto c = col + dc;
                // Out of bounds
                if (r < 0 || c < 0 || r >= ROWS || c >= COLS) {
                    continue;
                }
                if (grid[r][c] == FRESH) {
                    grid[r][c] = ROTTEN;
                    open.emplace(r, c);
                    --fresh_counter;
                }
            }
 
            // Increment the minute
            // After we finish processing one full BFS layer and the queue still contains
            //   newley rotten fruit, one minute has ellapsed.
            if (open_size == 0) {
                if (!open.empty()) {
                    ++minute;
                }
                open_size = open.size();
            }
        }
 
        // If we exit with fruit still in the queue, then we have stable state
        //  and didn't rot all fruit
        return fresh_counter == 0 ? minute : -1;
    }
};