Have you ever wondered how fast a virus can spread in a city? Or how quickly a rotten fruit can spoil others around it? Today, we’ll explore a fascinating problem known as Rotting Oranges, where fresh oranges get infected by their rotten neighbors over time. We’ll solve it using Breadth-First Search (BFS), a classic algorithm for spreading effects across grids.

Let’s dive in!

The Problem Statement 📝

Imagine you’re given a grid (like a chessboard) where:

1 represents a fresh orange 🍊
2 represents a rotten orange 🤢
0 represents an empty cell ⬜

Rotten oranges spread their infection to adjacent fresh oranges every minute. The question is:

👉 What is the minimum time required to rot all the fresh oranges?

If it's impossible to rot all the oranges, return -1.

Example Input & Output

Input Grid:

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

Output:

Explanation: It takes 4 minutes to infect all the fresh oranges. If any fresh orange is left uninfected, return -1.

The Plan: How to Solve It?

The best way to solve this problem is using Breadth-First Search (BFS). Why? Because BFS is perfect for spreading effects level-by-level—just like waves in water or an infection in a city.

Steps to Solve

1. Find all the initially rotten oranges and add them to a queue.
2. Count the fresh oranges in the grid.
3. Use BFS to spread the infection from rotten oranges to fresh ones, updating their state in the grid.
4. Track the time taken for all fresh oranges to rot.
5. If any fresh orange remains uninfected, return -1; otherwise, return the time taken.

The Code: BFS in Action!

Here’s the full Dart implementation of our solution:

class Solution {
  int orangesRotting(List<List<int>> grid) {
    List<List<int>> directions = [
      [1, 0], [-1, 0], [0, 1], [0, -1]
    ]; // Directions for adjacent cells (down, up, right, left)

    List<List<int>> queue = []; // Queue to store rotten oranges
    int fresh = 0, time = 0;
    int rows = grid.length, cols = grid[0].length;

    // Step 1: Initialize the queue with all initially rotten oranges and count fresh oranges
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        if (grid[i][j] == 2) {
          queue.add([i, j]);
        } else if (grid[i][j] == 1) {
          fresh++;
        }
      }
    }

    // Step 2: Process the queue in BFS fashion
    while (queue.isNotEmpty && fresh > 0) {
      int size = queue.length;
      for (int k = 0; k < size; k++) {
        List<int> rotten = queue.removeAt(0); // Dequeue
        int i = rotten[0], j = rotten[1];

        for (var dir in directions) {
          int newRow = i + dir[0];
          int newCol = j + dir[1];

          // Check if the new position is valid and has a fresh orange
          if (newRow >= 0 && newRow < rows &&
              newCol >= 0 && newCol < cols &&
              grid[newRow][newCol] == 1) {
            grid[newRow][newCol] = 2; // Make it rotten
            queue.add([newRow, newCol]); // Enqueue the new rotten orange
            fresh--; // Reduce the fresh orange count
          }
        }
      }
      time++; // Increment time after processing all rotten oranges of the current round
    }

    return fresh == 0 ? time : -1; // If all fresh oranges are rotten, return time; otherwise, return -1
  }
}

Breaking Down the Code

1. Storing Initial Rotten Oranges

We loop through the grid and add rotten oranges (2s) to a queue. We also count how many fresh oranges (1s) exist.

2. Using BFS to Spread Rotting

We process the queue level by level:

Take all rotten oranges at the current minute.
Try to rot their four adjacent neighbors.
If a fresh orange gets infected, add it to the queue.
Reduce the count of fresh oranges.

3. Tracking Time

Each BFS level represents one minute. We increase time only after all rotten oranges in the queue are processed for that level.

4. Checking If All Oranges Rotted

At the end, if fresh == 0, we return the time taken; otherwise, return -1.

Complexity Analysis

Factor	Complexity
Time Complexity	*O(NM)** (Each cell is visited at most once)
Space Complexity	*O(NM)** (Queue stores the worst-case grid size)

This solution efficiently processes the grid without redundant checks and is optimal for this problem. 🚀

Final Thoughts

The Rotting Oranges problem is a great example of how BFS can be used in real-world scenarios like virus spread, fire outbreaks, or even social influence propagation. By using a queue-based level-wise traversal, we ensure that every fresh orange rots in the shortest possible time.

If you enjoyed this, try modifying the grid to simulate different spread scenarios and test the robustness of this BFS approach!

Happy Coding! 🚀

The Rotting Oranges Problem: A BFS Journey Through a Grid

Table of contents