New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Rotting Oranges

Contributed by

Ratnesh

Medium

0/80

Avg time to solve 30 mins

Success Rate 85 %

1 upvotes

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, Constraints, 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

Auto

Console