+1-5714784200

Similar Problems

Similar Problems not available

Rotten Oranges - Leetcode Solution

Companies:

LeetCode:  Rotten Oranges Leetcode Solution

Difficulty: Unknown

Topics: graphs  

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 .
    enter image description here

    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
    enter image description here
  • At t = 1, the cells neighboring to cell 1, 1 also become rotten.
    enter image description here
  • At t = 2, the remaining fresh orange at 0, 2 also becomes rotten.
    enter image description here

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:

Rotten Oranges Solution Code

1