Rotting Oranges

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
126 upvotes
Asked in companies
MicrosoftAmazonApple

Problem statement

You have been given a grid containing some oranges. Each cell of this grid has one of the three integers values:

  • Value 0 - representing an empty cell.
  • Value 1 - representing a fresh orange.
  • Value 2 - representing a rotten orange.
  • Every second, any fresh orange that is adjacent(4-directionally) to a rotten orange becomes rotten.

    Your task is to find out the minimum time after which no cell has a fresh orange. If it's impossible to rot all the fresh oranges then print -1.

    Note:
    1. The grid has 0-based indexing.
    2. A rotten orange can affect the adjacent oranges 4 directionally i.e. Up, Down, Left, Right.
    
    Detailed explanation ( Input/output format, Notes, Images )
    Input Format:
    The first line of input contains two single space-separated integers 'N' and 'M' representing the number of rows and columns of the grid 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 <= 500
    1 <= M <= 500
    0 <= grid[i][j] <= 2
    
    Time Limit: 1 sec
    
    Sample Input 1:
    3 3
    2 1 1
    1 1 0
    0 1 1 
    
    Sample Output 1:
    4
    
    Explanation of Sample Input 1:
    Minimum 4 seconds are required to rot all the oranges in the grid as shown below.
    

    alt text

    Sample Input 2:
    3 3
    2 1 0
    0 1 1
    1 0 1
    
    Sample Output 2:
    -1
    
    Explanation of Sample Input 2:
    The bottom left corner fresh orange (row 2, column 0) has no adjacent oranges. Hence, it's impossible to rot it.
    
    Hint

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

    Approaches (2)
    Naïve Solution

    The idea is very simple and naive. We will process the rotten oranges second by second. Each second, we rot all the fresh oranges that are adjacent to the already 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. 2 because then we won’t able to differentiate between the current processing cells and the cells which are going to be processed in the next traversal. So, we will mark them as value 3. More formally, we will be marking the adjacent cells as ‘CURR_ROTTEN’ + 1 in each traversal of the grid.

     

    Here is the complete algorithm.

    • Initialize ‘TIME’ to 0 and ‘CURR_ROTTEN’ to 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 element of the grid is equal to ‘CURR_ROTTEN’ then we have to process this rotten orange.
        • So we will assign the adjacent elements to (‘CURR_ROTTEN’ + 1), if the adjacent 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.
    • At last, we will traverse the grid and check if there is any fresh orange left i.e. a cell with value 1. If found, return -1.
    • 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 end up traversing the whole grid max(N, M) times. This will happen when all the cells have value 1 except a corner cell having value 2.

    Space Complexity

    O(1).

     

    Constant space is used.

    Video Solution
    Unlock at level 3
    (75% EXP penalty)
    Code Solution
    (100% EXP penalty)
    Rotting Oranges
    Full screen
    Console