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)