Rotting Oranges

Problem

You are given an m x n grid representing a box of oranges. Each cell in the grid can have one of three values:

Every minute, any fresh orange that is adjacent (4-directionally: up, down, left, right) to a rotten orange becomes rotten.

Write a function that takes this grid as input and returns the minimum number of minutes that must elapse until no cell has a fresh orange. If it is impossible to rot every fresh orange, return -1.

Example 1

Input:

grid = [
["R", "F"],
["F", "F"],
]

Output: 2

Explanation:

After Minute 1: The rotting orange at grid[0][0] rots the fresh oranges at grid[0][1] and grid[1][0]. After Minute 2: The rotting orange at grid[1][0] (or grid[0][1]) rots the fresh orange at grid[1][1].

So after 2 minutes, all the fresh oranges are rotten.

Example 2

Input:

grid = [
["R", "E"],
["E", "F"],
]

Output: -1

Explanation:

The two adjacent oranges to the rotten orange at grid[0][0] are empty, so after 1 minute, there are no fresh oranges to rot. So it is impossible to rot every fresh orange.

Example 3

Input:

grid = [
["R", "F", "F", "F"],
["F", "F", "F", "R"],
["E", "E", "F", "F"],
]

Output: 2

Explanation

We can model this problem as a graph where each cell is a node and the edges are the connections between adjacent cells.

The key to this problem is recognizing that we can simulate the rotting process using a breadth-first search (BFS) traversal of the graph (since any rotting orange will cause its neighbors to rot in the next minute).

Step 1: Initialize BFS Queue and Count Fresh Oranges

We can start by iterating over each cell in the grid and adding the position of all the rotten oranges to a queue. As we iterate, we can also count the number of fresh oranges in the grid - which will help us determine if there are any fresh oranges left after the BFS traversal.

Step 2: BFS Traversal

Next, we find all the oranges that will rot in the next minute. For each rotten orange in the BFS queue, we check if any of its neighbors are fresh oranges. If so, we turn the fresh orange into a rotten orange and add it to the queue to prepare for the next minute (shown in orange in the diagrams below). We also decrement the count of fresh oranges.

When we have finished processing all the rotten oranges in the queue, we increment the minute counter and repeat the process until there are no more fresh oranges left or the queue is empty.

If fresh_oranges is 0, then all oranges have become rotten, and we return the number of minutes it took to make all the oranges rotten. Otherwise, we return -1, as not all oranges can become rotten.

Solution

from collections import deque

class Solution:
    def rotting_oranges(self, grid):
        if not grid:
            return -1

        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh_oranges = 0

        # Step 1: Initialize BFS Queue and Count Fresh Oranges
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "R":
                    queue.append((r, c))
                elif grid[r][c] == "F":
                    fresh_oranges += 1


        # Step 2: Perform BFS to Simulate Rotting Process
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        minutes = 0
        while queue and fresh_oranges > 0:
            minutes += 1

            # process all the rotten oranges at the current minute
            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] == "F":
                        grid[nx][ny] = "R"
                        fresh_oranges -= 1
                        queue.append((nx, ny))

        return minutes if fresh_oranges == 0 else -1

class Solution {
    public int rottingOranges(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return -1;
        }

        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int freshOranges = 0;

        // Step 1: Initialize BFS Queue and Count Fresh Oranges
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 'R') {
                    queue.offer(new int[]{r, c});
                } else if (grid[r][c] == 'F') {
                    freshOranges++;
                }
            }
        }

        // Step 2: Perform BFS to Simulate Rotting Process
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int minutes = 0;
        while (!queue.isEmpty() && freshOranges > 0) {
            minutes++;

            // process all the rotten oranges at the current minute
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] pos = queue.poll();
                int x = pos[0], y = pos[1];
                for (int[] dir : directions) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];
                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 'F') {
                        grid[nx][ny] = 'R';
                        freshOranges--;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }

        return freshOranges == 0 ? minutes : -1;
    }
}

type Position struct {
    Row, Col int
}

func rottingOranges(grid [][]rune) int {
    if len(grid) == 0 {
        return -1
    }

    rows := len(grid)
    cols := len(grid[0])
    var queue []Position
    freshOranges := 0

    // Step 1: Initialize BFS Queue and Count Fresh Oranges
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == 'R' {
                queue = append(queue, Position{r, c})
            } else if grid[r][c] == 'F' {
                freshOranges++
            }
        }
    }

    // Step 2: Perform BFS to Simulate Rotting Process
    directions := []Position{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    minutes := 0
    for len(queue) > 0 && freshOranges > 0 {
        minutes++

        // process all the rotten oranges at the current minute
        levelSize := len(queue)
        for i := 0; i < levelSize; i++ {
            pos := queue[0]
            queue = queue[1:]
            x, y := pos.Row, pos.Col
            for _, dir := range directions {
                nx := x + dir.Row
                ny := y + dir.Col
                if nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 'F' {
                    grid[nx][ny] = 'R'
                    freshOranges--
                    queue = append(queue, Position{nx, ny})
                }
            }
        }
    }

    if freshOranges == 0 {
        return minutes
    }
    return -1
}

class Solution {
    rottingOranges(grid: string[][]): number {
        if (!grid || grid.length === 0) {
            return -1;
        }

        const rows = grid.length;
        const cols = grid[0].length;
        const queue: [number, number][] = [];
        let freshOranges = 0;

        // Step 1: Initialize BFS Queue and Count Fresh Oranges
        for (let r = 0; r < rows; r++) {
            for (let c = 0; c < cols; c++) {
                if (grid[r][c] === "R") {
                    queue.push([r, c]);
                } else if (grid[r][c] === "F") {
                    freshOranges++;
                }
            }
        }

        // Step 2: Perform BFS to Simulate Rotting Process
        const directions: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        let minutes = 0;
        while (queue.length > 0 && freshOranges > 0) {
            minutes++;

            // process all the rotten oranges at the current minute
            const levelSize = queue.length;
            for (let i = 0; i < levelSize; i++) {
                const [x, y] = queue.shift()!;
                for (const [dx, dy] of directions) {
                    const nx = x + dx;
                    const ny = y + dy;
                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] === "F") {
                        grid[nx][ny] = "R";
                        freshOranges--;
                        queue.push([nx, ny]);
                    }
                }
            }
        }

        return freshOranges === 0 ? minutes : -1;
    }
}