Rotten Oranges

Companies:
  • Amazon Interview Questions
  • Flipkart Interview Questions

In a given a 2 dimensional array of size mxn called grid, each cell can contain only three numbers 0, 1 and 2 .

  • If the cell contains 0 , it means that the cell is empty.
  • If the cell contains 1 , it means that the cell is filled with a fresh orange .
  • If the cell contains 2 , it means that the cell is filled with a rotten orange. In each second, a rotten orange can affect it\’s neighboring oranges (in 4 directions) and make them rotten. Print the number of seconds it will take to make every fresh orange in the grid rotten. If it is not possible to do so, then print -1

Example Test Cases

Sample Test Case 1

Input grid: [[0, 1, 0], [1, 2, 1], [0, 1, 0]]
Expected Output: 1
Explanation :

  • At t = 0 , this is the initial configuration
    Initial Configuration
  • At t = 1, the cells neighboring to cell 1, 1 also become rotten .

    Since all the fresh oranges have become rotten at t = 1, the answer is 1

Sample Test Case 2

Input grid: [[0, 1, 1], [1, 2, 1], [0, 1, 0]]
Expected Output: 1
Explanation:

  • At t = 0 , this is the initial configuration
  • At t = 1, the cells neighboring to cell 1, 1 also become rotten.
  • At t = 2, the remaining fresh orange at 0, 2 also becomes rotten.

Since, all the oranges become rotten at t = 2 , the answer is 2

Solution

By trying a few examples by hand, we can see that the amount of time it takes to get a cell rotten is equal to the distance of the cell from it\’s nearest rotten cell.

In case of test case 1, all the fresh cells were at a distance of 1 from their nearest rotten cell, and therefore the time taken as 1.

In case of test case 2, the cell at location 0, 2 is at a distance of 2 units from the rotten cell 1, 1 . Therefore the time taken was 2 seconds.

We can model the grid in the form of a graph and to compute the distance for every node, we can apply standard bfs algorithm using a queue as shown below. Since, there can be multiple rotten cells, we will push all those cells in the queue first and then continue with the BFS as shown in the code below:

Scroll to Top