19. Rotten Oranges

Given an n x m grid, where each cell has the following values : 

2 - represents a rotten orange

1 - represents a Fresh orange

0 - represents an Empty Cell

Every minute, if a fresh orange is adjacent to a rotten orange in 4-direction ( upward, downwards, right, and left ) it becomes rotten. 

Return the minimum number of minutes required such that none of the cells has a Fresh Orange. If it's not possible, return -1.

Example 1:

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

Output: -1

Explanation: Orange at (3,0) cannot be rotten.

Example 2:

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

Output: 4

Explanation:

Now Your Turn!

Pick the correct output for the given input

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

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  •   1 <= n, m <= 500
  •   grid[i][j] == 0 or 1 or 2

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
class Solution{
public:
int orangesRotting(vector<vector<int>> &grid) {
}
};
Test Case

Input:

Grid
to save your code