Rotting Oranges - Java Solution

1. Introduction

This blog post addresses the "Rotting Oranges" problem, a typical challenge in grid and BFS (Breadth-First Search) algorithm applications. The scenario involves a grid where each cell can be an empty cell, a fresh orange, or a rotten orange. The task is to determine the minimum time required for all fresh oranges to become rotten, given that each minute, fresh oranges adjacent to rotten ones also become rotten.

Problem

Given an m x n grid where each cell can be either an empty cell (0), a fresh orange (1), or a rotten orange (2), the objective is to return the minimum number of minutes that must pass until no cell has a fresh orange. If it's impossible for all oranges to become rotten, return -1.

2. Solution Steps

1. Use BFS to simulate the rotting process of oranges.

2. Start by adding all the positions of rotten oranges to a queue.

3. Process the queue in a BFS manner, rotting adjacent fresh oranges and tracking time elapsed.

4. After the BFS, check if any fresh oranges remain. If so, return -1.

5. If all oranges have become rotten, return the time elapsed.

3. Code Program

import java.util.LinkedList;
import java.util.Queue;

public class RottingOranges {
    public static void main(String[] args) {
        int[][] grid = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
        System.out.println(orangesRotting(grid)); // Test the function
    }

    // Function to find the minimum time for all oranges to rot
    public static int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return -1;
        }
        int freshOranges = 0;
        Queue<int[]> queue = new LinkedList<>();

        // Initialize the queue with all rotten oranges and count fresh oranges
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    freshOranges++;
                }
            }
        }

        if (freshOranges == 0) return 0; // No fresh oranges
        int minutes = 0;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 4-directional movement

        // Process the queue in a BFS manner
        while (!queue.isEmpty() && freshOranges > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] pos = queue.poll();
                for (int[] dir : directions) {
                    int x = pos[0] + dir[0], y = pos[1] + dir[1];
                    if (x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 1) {
                        grid[x][y] = 2; // Rot the fresh orange
                        freshOranges--;
                        queue.offer(new int[]{x, y});
                    }
                }
            }
            minutes++; // Increase time after each level of BFS
        }

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

Output:

4

Explanation:

1. orangesRotting: This function calculates the minimum time required for all fresh oranges to rot.

2. It first counts the number of fresh oranges and initializes a queue with the positions of all rotten oranges.

3. If there are no fresh oranges, the function immediately returns 0.

4. Using BFS, the function processes each level of the grid. For each rotten orange, it attempts to rot adjacent fresh oranges in all four directions.

5. After processing each level of the grid (which represents one minute), the time counter is incremented.

6. If there are still fresh oranges left after the BFS, it means not all oranges can rot, and the function returns -1.

7. If all fresh oranges become rotten, the function returns the total time taken.

8. This approach efficiently models the spread of rot using BFS, ensuring that the minimum time to rot all oranges is computed.