Rotten Oranges

Link : Rotting Oranges

Problem Statement

You are given a 2D grid where:

• 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 minimum number of minutes that must elapse until no cell has a fresh orange.
If it is not possible, 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: Orange at (2, 0) can never rot.

Constraints

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 100

• grid[i][j] is 0, 1, or 2

Intuition

This is a classic multi-source BFS problem.

• Each initially rotten orange (value 2) is a source.

• Each minute, rotting spreads to adjacent fresh oranges.

• Each level in BFS represents one minute.

• The goal is to simulate the infection process and track how long it takes.

• If any fresh orange is left unvisited, return -1.

Approach: Multi-Source BFS

Key Observations

1. All rotten oranges rot adjacent fresh oranges in parallel.

2. This makes it a good fit for Breadth-First Search starting from all sources simultaneously.

3. The queue contains positions of rotten oranges.

4. Time increments only after a full level is processed (i.e., after all oranges that rot in the current minute are processed).

Algorithm

1. Initialize:

   • Count total fresh oranges.

   • Add all initially rotten orange positions to a queue.

2. Process BFS:

   • While queue is not empty:

     • For each cell in the current queue (current minute):

       • Visit its four neighbors (up, down, left, right).

       • If neighbor is a fresh orange:

         • Mark it as rotten.

         • Add it to the queue.

         • Decrement the fresh count.

3. After BFS ends:

   • If fresh == 0, return the time taken.

   • Otherwise, return -1.

Java Code

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        Queue<int[]> queue = new LinkedList<>();
        int fresh = 0;

        // Step 1: Count fresh oranges and collect rotten ones
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
                if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }

        if (fresh == 0) return 0;

        int time = 0;
        int[][] directions = {{0,1}, {0,-1}, {1,0}, {-1,0}};

        // Step 2: Perform BFS
        while (!queue.isEmpty()) {
            int size = queue.size();
            boolean changed = false;

            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];

                for (int[] dir : directions) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];

                    if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;
                        queue.offer(new int[]{nx, ny});
                        fresh--;
                        changed = true;
                    }
                }
            }

            if (changed) time++;
        }

        return fresh == 0 ? time : -1;
    }
}

Dry Run

Input

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

Execution

• Initially fresh = 6

• Queue: [(0,0)]

Minute 1:

• (0,0) → rot (0,1), (1,0) → fresh = 4

Minute 2:

• (0,1), (1,0) → rot (0,2), (1,1) → fresh = 2

Minute 3:

• (0,2), (1,1) → rot (2,1) → fresh = 1

Minute 4:

• (2,1) → rot (2,2) → fresh = 0

All oranges rotten in 4 minutes.

Time and Space Complexity

Time Complexity: O(m × n)

• Each cell is processed once at most.

Space Complexity: O(m × n)

• Queue can hold all oranges in worst case.

Conclusion

• This is a standard multi-source BFS simulation problem.

• Level-order traversal naturally maps to the problem's time-based simulation.

• Ensuring that fresh oranges count is tracked accurately is crucial.

• If even one orange cannot rot due to isolation, the solution must return -1.