Rotten Oranges Matrix Problem using BFS

Graphs

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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

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❯

  1. Initialize a queue and count of fresh oranges.
  2. Add all initially rotten oranges to the queue with timestamp 0.
  3. While the queue is not empty:
    1. Pop an orange from the queue.
    2. For each of the 4 directions:
      1. If the adjacent cell has a fresh orange, rot it, decrement fresh count, and add to queue with incremented time.
  4. If fresh count becomes 0, return the last recorded time. Else return -1.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#define MAX 100

int queue[MAX][3], front = 0, rear = 0;

void enqueue(int r, int c, int t) {
    queue[rear][0] = r;
    queue[rear][1] = c;
    queue[rear][2] = t;
    rear++;
}

void dequeue(int *r, int *c, int *t) {
    *r = queue[front][0];
    *c = queue[front][1];
    *t = queue[front][2];
    front++;
}

int orangesRotting(int grid[3][3], int rows, int cols) {
    int fresh = 0, time = 0;
    int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) enqueue(r, c, 0);
            if (grid[r][c] == 1) fresh++;
        }
    }

    while (front < rear) {
        int r, c, t;
        dequeue(&r, &c, &t);
        if (t > time) time = t;

        for (int i = 0; i < 4; i++) {
            int nr = r + directions[i][0];
            int nc = c + directions[i][1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                grid[nr][nc] = 2;
                fresh--;
                enqueue(nr, nc, t + 1);
            }
        }
    }
    return fresh == 0 ? time : -1;
}

int main() {
    int grid[3][3] = {{2,1,1},{1,1,0},{0,1,1}};
    printf("Minutes to rot all oranges: %d\n", orangesRotting(grid, 3, 3));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(m * n)Even in the best case, we must scan the entire matrix to identify the initial rotten and fresh oranges.
Average CaseO(m * n)Each cell is visited at most once — either to enqueue it or to rot it through BFS.
Worst CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...