Close
Topic list
Rotting Oranges
MEDIUM
30 mins
Other topics
Problem solved
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Dynamic Programming
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
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.

# Rotting Oranges

Contributed by
Ratnesh
Medium
0/80
Avg time to solve 30 mins
Success Rate 85 %
Share

## Problem Statement

#### 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 )
##### 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
``````
Auto
Console