🌱 Keegan's Digital Garden

994. Rotting Oranges

4 min read

📝 Problem Details

input matrix grid of size m * n each cell in grid can have three possible values: 0 ⇒ empty cell 1 ⇒ fresh orange 2 ⇒ rotten orange every minute any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten return the min number of minutes that must elapse until there are no cells with a fresh orange return -1 if impossible

💭What Were My Initial Thoughts?

        // base case:
        // init traversal variables
        // init BFS queue
        // first pass through to locate the positions of the rotten oranges
        // push the location of each (2) into the queue
        // init directions vector (up,down,left,right)
        // BFS while the queue is not empty
            // keep a counter for the number of minutes (1 min == 1 while loop iteration)
        // get row and col variables from front of queue
        // pop queue
        // try move 1 in each direction from this rotten orange position
            // if its a fresh orange, add it to the queue
            // changes its value to rotten (2)
        // return counter

💡 Explanation of Solution

Similar to intuition with a few additional considerations:
- need to track fresh oranges in the first pass through
- if there are no fresh oranges at the start , return early with 0
- if fresh oranges remain after BFS, return -1 (some oranges can never rot)

⌛ Complexity Analysis

Time Complexity: O(m*n)
Space Complexity: O(m*n)
	Worst case: all oranges are rotten , and we store every cell in the queue

💻 Implementation of Solution

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        if (grid.empty()) return -1; // Edge case: empty grid
 
        int rows = grid.size();
        int cols = grid[0].size();
        queue<pair<int, int>> q; // BFS queue for rotten oranges
        int freshOranges = 0;    // Count of fresh oranges
        int minutes = 0;         // Time counter
 
        // Step 1: Initialize BFS queue with all rotten oranges & count fresh oranges
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    q.push({r, c});  // Add rotten orange to queue
                } else if (grid[r][c] == 1) {
                    freshOranges++;  // Count fresh oranges
                }
            }
        }
 
        // If no fresh oranges, return 0 immediately
        if (freshOranges == 0) return 0;
 
        // Step 2: BFS Directions (Right, Left, Down, Up)
        vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 
        // Step 3: BFS Processing
        while (!q.empty()) {
            int qSize = q.size();
            bool newRotten = false; // Track if any fresh oranges got rotten
 
            for (int i = 0; i < qSize; i++) {
                auto [row, col] = q.front();
                q.pop();
 
                for (auto [dr, dc] : directions) {
                    int newRow = row + dr;
                    int newCol = col + dc;
 
                    // Check bounds and if it's a fresh orange
                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == 1) {
                        grid[newRow][newCol] = 2; // Rotten now
                        q.push({newRow, newCol}); // Add to queue
                        freshOranges--; // Decrease fresh count
                        newRotten = true;
                    }
                }
            }
 
            if (newRotten) minutes++; // Increase time only if an orange rotted this round
        }
 
        // If there are still fresh oranges left, return -1 (impossible to rot all)
        return freshOranges == 0 ? minutes : -1;
    }
};

Graph View