Problem Description

Question

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.

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

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

Example 1:

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

Output: 4

Example 2:

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

Output: -1

Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]

Output: 0

Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1, or 2.

Solve it on LeetCode

Approaches

1. BFS (Breadth-First Search) Simulation

Intuition:

The problem is essentially about finding the shortest time it takes for all fresh oranges to become rotten, akin to a multi-source shortest path problem. The oranges that are initially rotten act as multiple starting points and rot adjacent fresh oranges in the four cardinal directions. We can utilize a breadth-first search (BFS) to simulate the process in levels, where each level represents one unit of time.

Steps:

Initialize the Queue and Variables:

Use a queue to implement BFS, starting with all initially rotten oranges.
Count the number of fresh oranges.
A time counter (minutes) to track the time it takes to rot all oranges.

BFS Process:

At each BFS level (each minute), process all the oranges in the queue (these are the oranges that rot in the current minute).
For each rotten orange, attempt to rot all adjacent fresh oranges.
If a fresh orange becomes rotten, decrement the fresh orange count and enqueue it.

Check Results:

If at the end of BFS, there are any remaining fresh oranges, it is impossible to rot all oranges, and we return -1.
Otherwise, return the time counter which now reflects the total minutes taken.

Edge Cases:

If there are no fresh oranges to begin with, return 0 since no time is required.
All oranges being rotten initially would also require 0 minutes.

Code:

Complexity Analysis

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell in the grid is processed at most once.
Space Complexity: O(n), due to the use of additional array.

Rotting Oranges

Ashish Pratap Singh