Rotting Oranges

Moderate

0/80

Average time to solve is 30m

Contributed by

2 upvotes

Asked in companies

Problem statement

You are given an integer grid of size ‘N’x’M’, and the cell of the grid contains either of the three values:

0 - An empty cell.

1 - A fresh orange.

2 - A rotten orange.

Every minute, any fresh orange adjacent(4-directionally) to a rotten orange becomes rotten.

You must return the minimum time after which no fresh oranges are left. Return -1 if it's impossible to rot all the fresh oranges.

Example:

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

Output: 2

At T=0, only orange at (0,0) is rotten.
At T=1, oranges at (0,0),(0,1) and (1,0) are rotten.
At T=2, oranges at (0,0),(0,1),(1,0),(0,2) and (1,1) are rotten. 
No fresh oranges are left after T=2.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains two single space-separated integers, 'N' and 'M', representing the grid's number of rows and columns, respectively.

The next 'N' lines contain 'M' single space-separated integers, each representing the rows of the grid.

Output Format:

The only line of output contains a single integer, i.e., The minimum time after which no cell has a fresh orange. 

If it's impossible to rot all oranges, print -1.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints:

1 <= N*M <= 10^5
0 <= grid[i][j] <= 2

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

2 
1

Explanation of Sample Input 1:

For the first case:

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

Output: 2

At T=0, only orange at (0,0) is rotten.
At T=1, oranges at (0,0),(0,1) and (1,0) are rotten.
At T=2, oranges at (0,0),(0,1),(1,0),(0,2) and (1,1) are rotten. 
No fresh oranges are left after T=2.

For the second case:

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

Output: 1

At T=0, only oranges at (0,0) and (1,1) are rotten.
At T=1, oranges at (0,0),(0,1),(1,0) and (1,1) are rotten. 
No fresh oranges are left after T=1.

Sample Input 2:

Sample Output 2:

4 
-1

Console