# Rotting Oranges
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rotting-oranges)
Canonical: https://scaleengineer.com/dsa/problems/rotting-oranges
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [Docusign](https://scaleengineer.com/companies/docusign), [Expedia](https://scaleengineer.com/companies/expedia), [Flipkart](https://scaleengineer.com/companies/flipkart), [Intuit](https://scaleengineer.com/companies/intuit), [Myntra](https://scaleengineer.com/companies/myntra), [Nutanix](https://scaleengineer.com/companies/nutanix), [Roblox](https://scaleengineer.com/companies/roblox), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [VMware](https://scaleengineer.com/companies/vmware), [Wix](https://scaleengineer.com/companies/wix), [eBay](https://scaleengineer.com/companies/ebay), [Lyft](https://scaleengineer.com/companies/lyft), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel), [PhonePe](https://scaleengineer.com/companies/phonepe), [Zepto](https://scaleengineer.com/companies/zepto), [X](https://scaleengineer.com/companies/x), [Zoox](https://scaleengineer.com/companies/zoox), [Anduril](https://scaleengineer.com/companies/anduril), [DP world](https://scaleengineer.com/companies/dp-world), [Informatica](https://scaleengineer.com/companies/informatica), [ZipRecruiter](https://scaleengineer.com/companies/ziprecruiter)
---
## Problem
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:**

![](https://assets.glich.co/dsa/rotting-oranges/image0.png) 

**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`.

# Approaches
## Brute Force Simulation
This approach directly simulates the rotting process minute by minute. In each time step, it performs a full scan of the grid to identify all fresh oranges that are adjacent to a rotten one. These oranges are then marked to become rotten in the next minute. The simulation continues until no more oranges can rot. Finally, it checks if any fresh oranges remain to determine if the task was possible.
**Time:** O((M * N)^2). In each minute of the simulation, we scan the entire grid, which takes O(M * N) time. The number of minutes could be up to M * N in the worst case (e.g., a long snake-like path of oranges). This results in a quadratic time complexity. · **Space:** O(M * N), where M and N are the dimensions of the grid. In the worst case, the `toRot` list could store coordinates for nearly all the cells.
**Pros:** Conceptually simple and easy to follow as it directly models the real-world process.
**Cons:** Highly inefficient due to repeated O(M*N) scans of the grid in each minute.; The time complexity of O((M*N)^2) makes it too slow for larger grids.
### Explanation
The brute-force method involves simulating the process in discrete time steps. We start by counting the initial number of fresh oranges. Then, we enter a loop that models the passing of time. In each iteration, which corresponds to one minute, we scan the entire grid. We use a temporary list to collect the coordinates of all fresh oranges that are adjacent to any rotten orange from the beginning of that minute. It's crucial to use a temporary list to ensure that an orange that turns rotten in the current minute doesn't cause another fresh orange to rot in the same minute, as rotting happens simultaneously. After the scan, we update the state of all oranges in the temporary list to rotten. We increment our minute counter and repeat the process. If a full pass occurs where no new oranges rot but fresh ones still exist, we know some are unreachable, and the task is impossible. The simulation ends when there are no more fresh oranges left.

```java
class Solution {
    public int orangesRotting(int[][] grid) {
        int freshCount = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    freshCount++;
                }
            }
        }

        if (freshCount == 0) {
            return 0;
        }

        int minutes = 0;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (freshCount > 0) {
            java.util.List<int[]> toRot = new java.util.ArrayList<>();
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == 1) {
                        for (int i = 0; i < 4; i++) {
                            int nr = r + dr[i];
                            int nc = c + dc[i];
                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 2) {
                                toRot.add(new int[]{r, c});
                                break; // Found a rotten neighbor, move to the next fresh orange
                            }
                        }
                    }
                }
            }

            if (toRot.isEmpty()) {
                return -1; // No oranges rotted, but fresh ones remain.
            }

            for (int[] orange : toRot) {
                // Use a temporary state to avoid chain reactions in the same minute.
                // An orange that becomes rotten now should only affect others in the *next* minute.
                // We mark with 3 first to distinguish from oranges rotten at the start of the minute.
                grid[orange[0]][orange[1]] = 3; 
            }
            
            // Now, finalize the state for the next minute's simulation.
            for (int[] orange : toRot) {
                grid[orange[0]][orange[1]] = 2;
            }

            freshCount -= toRot.size();
            minutes++;
        }

        return minutes;
    }
}
```
### Algorithm
*   Initialize `minutes = 0` and count the total number of `freshOranges`.
*   If `freshOranges` is 0, the process is already complete, so return 0.
*   Enter a loop that continues as long as there are fresh oranges remaining.
*   In each iteration (representing one minute), create a temporary list, `toRot`, to store the coordinates of fresh oranges that will become rotten in this minute.
*   Iterate through every cell `(r, c)` of the grid.
*   If a cell contains a fresh orange (`grid[r][c] == 1`), check its four neighbors.
*   If any neighbor is a rotten orange (`grid[r][c] == 2`), add the coordinates `(r, c)` to the `toRot` list and stop checking neighbors for this cell.
*   After scanning the entire grid, if the `toRot` list is empty, it means no more oranges can rot, but fresh ones still exist. This indicates an impossible scenario, so we break the loop.
*   For each orange in the `toRot` list, update its state in the grid to rotten (`2`) and decrement the `freshOranges` count.
*   Increment the `minutes` counter.
*   After the loop terminates, if `freshOranges` is 0, return `minutes`. Otherwise, return -1.

## Multi-source Breadth-First Search (BFS)
This problem can be modeled as finding the shortest path in an unweighted graph, which is a perfect use case for Breadth-First Search (BFS). We can treat this as a multi-source BFS problem, where all initially rotten oranges are the sources. The BFS explores the grid layer by layer, where each layer corresponds to one minute of time passing. This efficiently calculates the minimum time for all fresh oranges to become rotten.
**Time:** O(M * N). We perform an initial scan of the grid, which takes O(M * N). The subsequent BFS ensures that each cell is enqueued and dequeued at most once. Thus, the overall time complexity is linear with respect to the number of cells in the grid. · **Space:** O(M * N). In the worst-case scenario, the queue could hold all the cells in the grid (e.g., a checkerboard pattern of fresh and rotten oranges).
**Pros:** Optimal time complexity of O(M*N).; Efficiently handles the simultaneous rotting from multiple sources.; Guaranteed to find the minimum time if a solution exists.
**Cons:** Requires extra space for the queue, which can be up to O(M*N) in the worst case.
### Explanation
The optimal approach treats the grid as a graph and uses a multi-source Breadth-First Search (BFS). The sources of the BFS are all cells that initially contain a rotten orange.

First, we iterate through the grid once to identify all initial rotten oranges, adding their coordinates to a queue. During this scan, we also count the total number of fresh oranges. This initial count is crucial for the final check.

Then, the BFS begins. It proceeds in levels. Each level of the BFS corresponds to one minute of the rotting process. We use a loop that continues as long as there are rotten oranges in our queue to spread from. In each iteration of this main loop, we process all oranges currently in the queue (a single level). For each rotten orange we dequeue, we check its four neighbors. If a neighbor is a fresh orange, we change its state to rotten, add its coordinates to the queue for the next level, and decrement our `freshOranges` counter.

After the BFS completes (the queue is empty), we check if the `freshOranges` counter has reached zero. If it has, it means every fresh orange was reached and rotted, and we return the total minutes elapsed. If the counter is still greater than zero, it means some fresh oranges were isolated and could not be reached, so we return -1.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return -1;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;

        // Find initial rotten oranges and count fresh oranges
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    queue.offer(new int[]{r, c});
                } else if (grid[r][c] == 1) {
                    freshCount++;
                }
            }
        }

        if (freshCount == 0) {
            return 0;
        }

        int minutes = 0;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        // Start BFS from all initial rotten oranges
        while (!queue.isEmpty() && freshCount > 0) {
            minutes++;
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] point = queue.poll();
                for (int[] dir : directions) {
                    int r = point[0] + dir[0];
                    int c = point[1] + dir[1];

                    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != 1) {
                        continue;
                    }

                    grid[r][c] = 2;
                    queue.offer(new int[]{r, c});
                    freshCount--;
                }
            }
        }

        return freshCount == 0 ? minutes : -1;
    }
}
```
### Algorithm
*   Initialize a queue and add the coordinates of all initially rotten oranges (value 2).
*   Scan the grid to count the total number of `freshOranges` (value 1).
*   If `freshOranges` is 0, return 0.
*   Initialize `minutes = 0`.
*   Start a `while` loop that runs as long as the queue is not empty and there are still fresh oranges.
*   Inside the loop, increment `minutes` as we are processing a new level of rotting.
*   Get the current `levelSize` of the queue. This represents all oranges that became rotten in the previous minute.
*   Loop `levelSize` times:
    *   Dequeue a rotten orange's coordinates `(r, c)`.
    *   For each of its 4-directional neighbors `(nr, nc)`:
    *   Check if the neighbor is within grid boundaries and is a fresh orange (`grid[nr][nc] == 1`).
    *   If it is, update the grid `grid[nr][nc] = 2`, decrement `freshOranges`, and enqueue the new rotten orange's coordinates `(nr, nc)`.
*   After the main `while` loop finishes, check if `freshOranges` is 0. If it is, all oranges have rotted, so return `minutes`. Otherwise, some were unreachable, so return -1.

# Solutions
### Java

```java
class Solution {
public
  int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int cnt = 0;
    Deque<int[]> q = new LinkedList<>();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 2) {
          q.offer(new int[]{i, j});
        } else if (grid[i][j] == 1) {
          ++cnt;
        }
      }
    }
    int ans = 0;
    int[] dirs = {1, 0, -1, 0, 1};
    while (!q.isEmpty() && cnt > 0) {
      ++ans;
      for (int i = q.size(); i > 0; --i) {
        int[] p = q.poll();
        for (int j = 0; j < 4; ++j) {
          int x = p[0] + dirs[j];
          int y = p[1] + dirs[j + 1];
          if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
            grid[x][y] = 2;
            --cnt;
            q.offer(new int[]{x, y});
          }
        }
      }
    }
    return cnt > 0 ? -1 : ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} grid * @return {number} */ var orangesRotting = function ( grid ) { const m = grid . length ; const n = grid [ 0 ]. length ; let q = []; let cnt = 0 ; for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; ++ j ) { if ( grid [ i ][ j ] === 1 ) { cnt ++ ; } else if ( grid [ i ][ j ] === 2 ) { q . push ([ i , j ]); } } } const dirs = [ - 1 , 0 , 1 , 0 , - 1 ]; for ( let ans = 1 ; q . length && cnt ; ++ ans ) { let t = []; for ( const [ i , j ] of q ) { for ( let d = 0 ; d < 4 ; ++ d ) { const x = i + dirs [ d ]; const y = j + dirs [ d + 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n && grid [ x ][ y ] === 1 ) { grid [ x ][ y ] = 2 ; t . push ([ x , y ]); if ( -- cnt === 0 ) { return ans ; } } } } q = [... t ]; } return cnt > 0 ? - 1 : 0 ; };
```

### CPP

```cpp
class Solution {
public:
  int orangesRotting(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int cnt = 0;
    typedef pair<int, int> pii;
    queue<pii> q;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 2)
          q.emplace(i, j);
        else if (grid[i][j] == 1)
          ++cnt;
      }
    }
    int ans = 0;
    vector<int> dirs = {-1, 0, 1, 0, -1};
    while (!q.empty() && cnt > 0) {
      ++ans;
      for (int i = q.size(); i > 0; --i) {
        auto p = q.front();
        q.pop();
        for (int j = 0; j < 4; ++j) {
          int x = p.first + dirs[j];
          int y = p.second + dirs[j + 1];
          if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
            --cnt;
            grid[x][y] = 2;
            q.emplace(x, y);
          }
        }
      }
    }
    return cnt > 0 ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) q = deque() cnt = 0 for i in range(m): for j in range(n): if grid[i][j] == 2: q . append((i, j)) elif grid[i][j] == 1: cnt += 1 ans = 0 while q and cnt: ans += 1 for _ in range(len(q)): i, j = q . popleft() for a, b in [[0, 1], [0, - 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[x][y] == 1: cnt -= 1 grid[x][y] = 2 q . append((x, y)) return ans if cnt == 0 else - 1

```