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:

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.