Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Rotting Oranges
MEDIUM
30 mins
1 upvotes
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
Linked List
-
-
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
userLevel
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
yellow-spark
0/80
Avg time to solve 30 mins
Success Rate 85 %
Share
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 )
    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
    
    Reset Code
    Full screen
    Auto
    copy-code
    Console