Topics

# Rotting Oranges

Moderate
0/80
Average time to solve is 30m
Contributed by
1 upvote

## 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 )
Constraints:
``````1 <= N*M <= 10^5
0 <= grid[i][j] <= 2

Time Limit: 1 sec
``````
Sample Input 1:
``````2
3 3
2 1 0
1 1 0
0 0 0
2 2
2 1
1 2
``````
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:
``````2
3 3
2 1 1
1 1 0
0 1 1
3 3
2 1 0
0 1 1
1 0 1
``````
Sample Output 2:
``````4
-1
``````
Console