> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/graphs/rotting-oranges.md).

# Rotting Oranges

BFS

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

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MQit2i_PfHv7bHvaaV2%2F-MQivgNo-kZgnjCe6AEp%2FScreen%20Shot%202021-01-10%20at%205.53.08%20PM.png?alt=media\&token=3aa5369d-edc9-41df-8cdc-70b72c970e23)

### Thought Process

* This question is similar to **Walls and Gates**

* We will store all the rotten oranges ('2') in a queue while alos keeping track of how many fresh oranges we have. 

* We are applying BFS to search for the rotten oranges neighbors so we can rot them too. We are processing rotten oranges by level.

## Solution

```
from collections import deque 
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        
        
        q = deque()
        count_fresh = 0 # keep track of fresh oranges
        
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    q.append([i,j])
                elif grid[i][j] == 1:
                    count_fresh+=1
                    
        if count_fresh == 0:
            return 0
        
        c = 0
        direc = [[1,0], [-1,0],[0,-1], [0,1]]
        while q and count_fresh > 0:
            c+=1
            level_size = len(q)
            
            for _ in range(level_size):    
                coor = q.popleft()
                x = coor[0]
                y = coor[1]
                for i in direc:
                    newX = x+i[0] #new x-coor
                    newY = y+i[1] #new y-coor
                    
                    if newX < 0 or newX >= len(grid) or newY < 0 or newY == len(grid[0]):
                        continue
                        
                    if grid[newX][newY] == 0 or grid[newX][newY] == 2:
                        continue
                        
                    count_fresh-=1
                    
                    grid[newX][newY] = 2
                    q.append([newX,newY])
                    
            
        return c if count_fresh == 0 else -1
        


```

## Time Complexity

* **Time**: O(m\*n)
* **Space:** O(m\*n)