Rotten Oranges Matrix Problem using BFS

Problem Statement❯

You are given an m x n grid representing a box of oranges. Each cell of the grid can have one of the following values:

0: an empty cell
1: a fresh orange
2: a rotten orange

Each minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Your task is to return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Examples❯

Grid	Output	Description
[[2,1,1],[1,1,0],[0,1,1]]	4	All oranges become rotten in 4 minutes
[[2,1,1],[0,1,1],[1,0,1]]	-1	Some fresh oranges are unreachable
[[0,2]]	0	No fresh orange to rot
[[1]]	-1	One fresh orange with no rotten source
[[2,2,2],[2,1,2],[2,2,2]]	1	Fresh orange surrounded by rotten ones
[[2,1,1,0],[0,1,1,1],[1,0,1,0],[0,1,1,2]]	-1	Larger 4x4 grid with reachable fresh oranges
[[2,1,0,2],[1,1,1,1],[0,1,0,1],[2,1,1,2],[2,2,2,2]]	2	5x4 grid with multiple rotten sources

Visualization Player

Solution❯

Understanding the Problem

We are given a 2D grid (matrix) that represents a box of oranges. Each cell in the grid can have one of the following values:

0 — an empty cell (no orange)
1 — a fresh orange
2 — a rotten orange

Every minute, a rotten orange will cause all directly adjacent fresh oranges (up, down, left, right) to become rotten. Our task is to calculate the minimum number of minutes that must pass until no cell has a fresh orange. If it's not possible for all the fresh oranges to rot, we should return -1.

Step-by-Step Solution with Example

Step 1: Understand the input

Let’s consider the following input grid:

[
  [2,1,1],
  [1,1,0],
  [0,1,1]
]

Here, we have one rotten orange at the top-left corner (0,0), and the rest are fresh (1s), except a few empty cells (0s).

Step 2: Choose the right strategy

To simulate the spread of rot over time, we use Breadth-First Search (BFS). We treat all initially rotten oranges as the starting points of BFS and process them level by level (minute by minute).

Step 3: Initialize the BFS queue

We enqueue all the rotten oranges along with their time = 0. We also count how many fresh oranges are initially present. This helps us track when all fresh ones have been rotted.

Step 4: BFS traversal

For each rotten orange in the queue, we visit its four neighbors (up, down, left, right). If any neighbor is a fresh orange, we turn it rotten, decrement the fresh count, and enqueue it with time +1.

Step 5: Track the time

We maintain a variable time to track the number of minutes taken to rot all reachable fresh oranges. It is updated as we process new levels in the BFS queue.

Step 6: Check if all fresh oranges are rotted

Once the BFS is done, we check if any fresh oranges are left. If so, return -1 because they were unreachable. Otherwise, return the maximum time it took to rot all oranges.

Step 7: Apply to our example

Initially rotten orange at (0,0) rots its neighbors one by one:

Minute 1: (0,1), (1,0) become rotten
Minute 2: (0,2), (1,1)
Minute 3: (2,1)
Minute 4: (2,2)

All fresh oranges are now rotten. Total time taken: 4 minutes.

Edge Cases

Case 1: All oranges already rotten or no fresh oranges

If there are no fresh oranges, return 0 since no rotting is needed.

Case 2: Fresh oranges exist but no rotten oranges

There is no way to rot the fresh oranges. Return -1.

Case 3: Some fresh oranges are isolated

If a fresh orange is completely surrounded by empty cells or other fresh ones and cannot be reached by a rotten one, it will remain fresh. Again, return -1.

Finally

This problem helps us understand how to simulate processes over time using BFS in a grid. Always begin by identifying the sources (in this case, initially rotten oranges) and process outward in waves. By tracking time and counting fresh oranges, we can determine the exact moment all fresh oranges have been infected—or if it's impossible.

Algorithm Steps❯

Initialize a queue and count of fresh oranges.
Add all initially rotten oranges to the queue with timestamp 0.
While the queue is not empty:

Pop an orange from the queue.
For each of the 4 directions:

If the adjacent cell has a fresh orange, rot it, decrement fresh count, and add to queue with incremented time.

If fresh count becomes 0, return the last recorded time. Else return -1.

Code

JavaScript

function orangesRotting(grid) {
  const rows = grid.length, cols = grid[0].length;
  const queue = [];
  let fresh = 0, time = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c, 0]);
      if (grid[r][c] === 1) fresh++;
    }
  }

  const directions = [[0,1],[1,0],[0,-1],[-1,0]];

  while (queue.length > 0) {
    const [r, c, t] = queue.shift();
    time = Math.max(time, t);
    for (const [dr, dc] of directions) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
        grid[nr][nc] = 2;
        fresh--;
        queue.push([nr, nc, t + 1]);
      }
    }
  }

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

console.log("Minutes to rot all oranges:", orangesRotting([[2,1,1],[1,1,0],[0,1,1]])); // 4
console.log("Minutes to rot all oranges:", orangesRotting([[2,1,1],[0,1,1],[1,0,1]])); // -1

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(m * n)	Even in the best case, we must scan the entire matrix to identify the initial rotten and fresh oranges.
Average Case	O(m * n)	Each cell is visited at most once — either to enqueue it or to rot it through BFS.
Worst Case	O(m * n)	In the worst case, BFS will traverse every cell in the matrix to rot all reachable fresh oranges.

Space Complexity❯

O(m * n)

Explanation: In the worst case, the queue may hold all the oranges in the grid, especially if they're all rotten or become rotten one after another.

⬅ Previous TopicConnected Components in a Matrix

Next Topic ⮕Flood Fill Algorithm - Graph Based

Comments

Loading comments...