Rotting Oranges

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.

Examples

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.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Solution

Method 1 - BFS with Level by Level Approach

The problem can be visualised as a graph traversal problem where:

• Each orange in the grid serves as a node.
• The adjacency of nodes corresponds to the 4-directional neighbours in the grid.

We can use BFS around rotten oranges. Basically we have to count BFS waves, which is same as number of levels when we iterate on Tree level by level. Also, we should keep track of fresh oranges, as if there are fresh oranges remaining at the end of BFS, we should just return.

By using a breadth-first search (BFS) approach starting from all initially rotten oranges, we track:

1. The spread of rot minute by minute.
2. If any fresh orange remains unreachable, we return -1.

Key points:

• Use a queue to process rotten oranges in layers, as BFS computes the shortest path for graph traversal.
• Count the total fresh oranges initially.
• If after BFS traversal some fresh oranges are still left, the answer is -1.

Approach

1. Initial Setup:
   • Count the number of fresh oranges.
   • Add all rotten oranges to a queue.
   • Track time elapsed during the propagation.
2. Breadth-First Search (BFS):
   • For each rotten orange, rot its adjacent fresh oranges.
   • Track which oranges become rotten during each minute.
3. Exit Conditions:
   • If the queue is empty but there are fresh oranges remaining, return -1.
   • Otherwise, return the total time elapsed.

Code

Java

public class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;
        
        // Step 1: Count fresh oranges and add rotten oranges to the queue
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) { // Rotten orange
                    queue.add(new int[]{r, c});
                } else if (grid[r][c] == 1) { // Fresh orange
                    freshCount++;
                }
            }
        }
        
        // Step 2: BFS to rot fresh oranges
        int minutesElapsed = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        while (!queue.isEmpty() && freshCount > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                
                for (int[] dir : directions) {
                    int nx = curr[0] + dir[0], ny = curr[1] + dir[1];
                    
                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2; // Make fresh orange rotten
                        freshCount--;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
            minutesElapsed++;
        }
        
        // Step 3: Check if all fresh oranges were rotted
        return freshCount == 0 ? minutesElapsed : -1;
    }
}

Python

class Solution:
    def orangesRotting(self, grid):
        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh_count = 0
        
        # Step 1: Count fresh oranges and add rotten oranges to queue
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:  # Rotten orange
                    queue.append((r, c))
                elif grid[r][c] == 1:  # Fresh orange
                    fresh_count += 1
        
        # Step 2: BFS to rot fresh oranges
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        minutes_elapsed = 0
        
        while queue and fresh_count > 0:
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                        grid[nx][ny] = 2  # Make fresh orange rotten
                        fresh_count -= 1
                        queue.append((nx, ny))
            minutes_elapsed += 1

        # Step 3: Check if all fresh oranges were rotted
        return minutes_elapsed if fresh_count == 0 else -1

Complexity

• ⏰ Time complexity: O(m * n). Every orange is visited once during BFS.
• 🧺 Space complexity: O(m * n). The queue may contain all rotten oranges.