Rotten Oranges Problem

Problem Summary

You are given a grid:

• 0 → empty cell

• 1 → fresh orange

• 2 → rotten orange

A rotten orange spreads rot to its 4-direction neighbors every 1 unit time.

Task:

Find the minimum time required to rot all fresh oranges.
If impossible → return -1.

Key Insight

This is a multi-source BFS problem.

Why?

• Multiple rotten oranges start spreading simultaneously

• Each level of BFS = 1 unit of time

Intuition

Think of rotten oranges like:

“multiple fire sources spreading at the same time”

We process:

• All initial rotten oranges first

• Then spread level by level

Approach (BFS)

Step 1: Initialize Queue

Push all rotten oranges (2) into a queue.

Step 2: Count fresh oranges

Track number of fresh oranges (1).

Step 3: BFS traversal

For each level:

• Rot adjacent fresh oranges

• Add newly rotten oranges to queue

• Increase time

Step 4: Final check

If fresh oranges remain → return -1

Example

Input:

2 1 0
1 1 1
0 1 2

Process:

• Time = 0 → initial rotten

• Time = 1 → first spread

• Time = 2 → final spread

Output:

2

Java Code

import java.util.*;

class Solution {

    static class Cell {
        int r, c;
        Cell(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    public int orangesRot(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;

        Queue<Cell> q = new LinkedList<>();
        int fresh = 0;

        // Step 1: add all rotten oranges
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 2) {
                    q.add(new Cell(i, j));
                } else if (mat[i][j] == 1) {
                    fresh++;
                }
            }
        }

        // If no fresh oranges
        if (fresh == 0) return 0;

        int time = 0;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        // Step 2: BFS
        while (!q.isEmpty()) {
            int size = q.size();
            boolean rotted = false;

            for (int i = 0; i < size; i++) {
                Cell cur = q.poll();

                for (int d = 0; d < 4; d++) {
                    int nr = cur.r + dr[d];
                    int nc = cur.c + dc[d];

                    if (nr >= 0 && nr < n && nc >= 0 && nc < m &&
                        mat[nr][nc] == 1) {

                        mat[nr][nc] = 2;
                        fresh--;
                        q.add(new Cell(nr, nc));
                        rotted = true;
                    }
                }
            }

            if (rotted) time++;
        }

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

Complexity

• Time Complexity: O(n × m)

  • Each cell processed at most once

• Space Complexity: O(n × m)

  • Queue in worst case

Key Takeaways

• This is a multi-source BFS problem

• Each BFS level = 1 unit time

• Always push all sources initially

• Track remaining fresh nodes for impossibility check

Pattern Recognition

If you see:

• Spreading / infection / fire / rot / contamination

• Multiple starting points

• Minimum time required

Think: MULTI-SOURCE BFS

Summary

This problem is a classic application of multi-source Breadth-First Search where multiple starting points propagate changes simultaneously across a grid. By processing the grid level by level, each representing a unit of time, we can efficiently determine the minimum time required to rot all fresh oranges or detect if it is impossible. The approach highlights an important BFS pattern frequently used in grid-based and shortest-time propagation problems.