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.
Comments
Loading comments...