Rotting Oranges 🍊

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! 🙏