Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Rotting Oranges

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in companies
AmazonSwiggySoroco

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
    
    Full screen
    Console