Rotting Oranges

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
2 upvotes
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 )
    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:
    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
    Hint

     Try the brute force approach. Every second, rot all fresh oranges adjacent to the rotten oranges.

    Approaches (2)
    Brute Force

    The idea is elementary and naive. We will process the rotten oranges second by second. Each second, we rot all the fresh oranges adjacent to the rotten oranges. The time by which there are no rotten oranges left to process will be our minimum time.

     

    In the first traversal of the grid, we will process all the cells with value 2 (rotten oranges). We will also mark their adjacent cells as rotten for the next traversal. Now, we can’t mark them by assigning the same value, i.e., two, because then we won’t be able to differentiate between the current processing cells and the cells processed in the next traversal. So, we will mark them as value 3. More formally, we will mark the adjacent cells as ‘CURR_ROTTEN’ + 1 in each grid traversal.

     

    Here is the complete algorithm.

    1. Initialize ‘TIME’ to 0 and ‘CURR_ROTTEN’ to 2.
    2. Loop until there is no rotten orange left to process.
      • Initialize ‘NOT_FOUND’ to true.
      • We will run a nested loop and traverse the grid.
        • If the grid element is equal to ‘CURR_ROTTEN’, then we must process this rotten orange.
        • So we will assign the adjacent elements to (‘CURR_ROTTEN’ + 1) if the adjoining orange is fresh (value is 1) and ‘NOT_FOUND’ to false.
      • If ‘NOT_FOUND’ is true, break.
      • Else, increment ‘TIME’ by 1.
      • Increment ‘CURR_ROTTEN’ by 1.
    3. At last, we will traverse the grid and check if there is any fresh orange left, i.e., a cell with a value of 1. If found, return -1.
    4. Else return time elapsed, i.e., maximum of ‘TIME’ - 1 and 0.
    Time Complexity

    O(N * M * max(N, M)), where N and M are the numbers of rows and columns of the grid, respectively.

     

    In the worst-case scenario, we might traverse the whole grid max(N, M) times. This will happen when all the cells have a value of 1 except a corner cell having a value of 2.

     

    Hence the time complexity is O(N * M * max(N, M)).

    Space Complexity

    Constant space is used.

     

    Hence the time complexity is O( 1 ).

    Code Solution
    (100% EXP penalty)
    Rotting Oranges
    Full screen
    Console