In this tutorial, i am going to discuss a very interesting problem rotting oranges (minimum time required to rot all fresh oranges).
Given an m*n grid where each cell in the matrix can have values 0, 1 or 2.
0 represents an empty cell
1 represents cells have fresh oranges
2 represents cells have rotten oranges
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
For example –
In the below example, we have given the grid, it takes 4 minute to rot all fresh oranges.
This is the problem statement, let’s think how we can solve this problem efficiently.
Rotting Oranges – Java Code & Explanation
In this problem, we have to find the time taken to rot all fresh oranges, if it’s not possible then return -1.
How to approach this problem?
i) To solve this problem, the first step is to find all the oranges that are initially rotten.
ii) In the next one minute, these rotten oranges will rot the neighbouring fresh oranges. And this process will continue till all the rotten oranges have rot their adjacent fresh oranges.
Imagine this process in breadth first manner (level by level). First we track all the rotten oranges (Imagine it is at level 0). Then these rotten oranges rot their adjacent fresh oranges and so on (In level 1, 2 etc). So, the time required to rot all oranges is equal to the number of levels.
We have to handle one more case. Suppose, if there are no fresh oranges in the grid. In that case simply return 0.
Steps to solve this problem –
i) Declare a queue to keep all the rotten oranges.
ii) Iterate the grid and add all the rotten oranges in the queue. Also, declare one variable to store the count of fresh oranges.
iii) If there is no fresh oranges in grid then return zero. Else run a loop dequeue the rotten oranges from a queue and rot all the adjacent oranges. In this process decrement the count of fresh oranges and enqueue rotten oranges in a queue. After this process increment the value of count (which keeps track of minute).
Repeat this process until we have no more rotten oranges.
If the number of fresh oranges after the entire process is still not zero, then return -1 indicating that it’s impossible to rot all the oranges.
Else return the time required to rot all the oranges.
The time complexity of this approach is O(m*n) where m and n is the length of row and column.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
//Attributes corresponding to row and col class Index { int row; int col; public Index(int row, int col) { this.row = row; this.col = col; } } class Solution { public int orangesRotting(int[][] grid) { //Declare index Queue<Index> qu = new LinkedList(); //variable to count fresh oranges int freshCount = 0; //Traverse a grid for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 2) { qu.add(new Index(i, j)); } else if (grid[i][j] == 1) { freshCount++; } } } //Move in four direction int[][] direction = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int count = 0; while (!qu.isEmpty() && freshCount > 0) { count++; int size = qu.size(); while (size-- > 0) { Index temp = qu.poll(); for (int[] d : direction) { int row = temp.row + d[0]; int col = temp.col + d[1]; if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length || grid[row][col] == 0 || grid[row][col] == 2) continue; qu.add(new Index(row, col)); grid[row][col] = 2; freshCount--; } } } return freshCount == 0 ? count : -1; } } |
