← Back to DSA
#994

Rotting Oranges

Medium
ArrayBreadth-First SearchMatrix
Solve on LeetCode ↗

Rotting Oranges

Problem

We are given a grid where:

  • 0 means an empty cell
  • 1 means a fresh orange
  • 2 means a rotten orange

Every minute, any fresh orange that is directly adjacent to a rotten orange in the four main directions becomes rotten.

We need to return:

  • the minimum number of minutes required so that no fresh orange remains
  • -1 if some fresh orange can never become rotten

Key Insight

This is a classic multi-source BFS problem.

Why multi-source?

Because all initially rotten oranges start spreading rot at the same time.

So instead of running BFS from one rotten orange, we push all rotten oranges into the queue first with time 0.

Then BFS naturally spreads the infection level by level, which matches the "minute by minute" behavior in the problem.

Approach

1. Build the initial queue

We scan the whole grid once.

  • if a cell contains a rotten orange, push it into the queue with duration 0
  • if a cell contains a fresh orange, mark it as fresh in visited
  • if a cell is empty, mark it as unusable

This gives us the correct starting points for BFS.

2. Spread rot using BFS

For each orange popped from the queue:

  • update the answer using its current time
  • try all four directions
  • if a neighboring cell contains a fresh orange, mark it rotten and push it with time currentTime + 1

Because BFS explores layer by layer, the first time we rot an orange is the minimum time needed to reach it.

3. Check for leftovers

After BFS finishes, if any fresh orange is still left in visited, that means it was unreachable.

So we return -1.

Otherwise, we return the maximum time seen during BFS.

Why This Works

The important observation is that all rotten oranges act simultaneously.

That is exactly what multi-source BFS models:

  • all initial rotten oranges are at level 0
  • oranges infected after 1 minute are at level 1
  • oranges infected after 2 minutes are at level 2

and so on.

So the farthest orange reached by BFS determines the total number of minutes needed.

Java Solution

This is your submission:

class Info {
    int x;
    int y;
    int duration;

    Info(int x, int y, int duration) {
        this.x = x;
        this.y = y;
        this.duration = duration;
    }
}

class Solution {
    public int orangesRotting(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] visited = new int[n][m];
        int ans = 0;

        Queue<Info> q = new LinkedList<>();

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {
                    q.offer(new Info(i, j, 0));
                    visited[i][j] = 2;
                } else if (grid[i][j] == 1){
                    visited[i][j] = 1;
                } else {
                    visited[i][j] = -1;
                }
            }
        }

        int[] rowDir = {0, 1, 0, -1};
        int[] colDir = {1, 0, -1, 0};

        while(!q.isEmpty()) {
            Info node = q.poll();
            int x = node.x;
            int y = node.y;
            int time = node.duration;

            ans = Math.max(ans,time);

            for(int i = 0; i < 4; i++) {
                int newX = x + rowDir[i];
                int newY = y + colDir[i];

                if(newX >=0 && newX < n && newY >= 0 && newY < m && visited[newX][newY]!=2 && grid[newX][newY] == 1) {
                    q.offer(new Info(newX, newY, time+1));
                    visited[newX][newY] = 2;
                }

            }

        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(visited[i][j] == 1) return -1;
            }
        }

        return ans;
    }
}

Walkthrough

Take:

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

Initially, the orange at (0, 0) is rotten, so it enters the queue with time 0.

Minute 1

It rots:

  • (0, 1)
  • (1, 0)

Minute 2

Those newly rotten oranges then rot:

  • (0, 2)
  • (1, 1)

Minute 3

Then:

  • (2, 1)

Minute 4

Finally:

  • (2, 2)

So the answer is 4.

Complexity Analysis

Time Complexity: O(n * m)

  • we scan the grid once to initialize the queue
  • in BFS, each cell is processed at most once
  • we scan once more to check if any fresh orange remains

Space Complexity: O(n * m)

  • the visited matrix takes O(n * m)
  • the queue can also take up to O(n * m) in the worst case

Common Mistakes

1. Starting BFS from only one rotten orange

That is incorrect because all rotten oranges spread at the same time.

2. Not marking an orange as rotten when pushing it

If we wait until pop time, the same fresh orange can be inserted into the queue multiple times.

Your solution handles this correctly by marking visited[newX][newY] = 2 immediately.

3. Forgetting the unreachable case

If BFS ends and some fresh orange is still left, we must return -1.

Small Note On Your Implementation

One thing I like in this solution is that the duration is stored directly inside the queue node.

That keeps the BFS very easy to read:

  • pop current orange
  • look at its time
  • push neighbors with time + 1

It is simple and maps nicely to the problem statement.

Related Problems

← Back to all solutions