This is a great problem looking at how to deal with grid problems.

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;

the value 1 representing a fresh orange;

the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) 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 instead.

### Example 1:

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

Output: 4

### Example 2:

Input: [[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: [[0,2]]

Output: 0

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

Since this problem deals with a grid you can already start thinking of two different techniques. Either you utilize a depth-first or breadth-first method.

### Solution 🙌

Looking at this I utilized a queue in a breadth-first traversal to solve this problem. First I iterate through the grid and add all rotten oranges to a list, this will give me a starting point. After I have gotten all initial rotten oranges I go through each rotten orange and convert it's neighbors to rotten if an orange exists. With a list of neighbors that have turned rotten, I add them to my rotten list with a counter denoting the "minute" that it turned. I use this minute each time I add a new set of neighbors to the rotten list.

Hope you liked this post, please follow and clap for more! Throw your implementations in the comments below! 🙏

## Top comments (0)