Introduction
In this series of "Leetcode" posts I will publish solutions to leetcode problems. It is true that you can find most/lots of leetcode solutions on the web, but I will try to post my solutions to problems that are interesting or to problems for which the solutions out there are not well explained and deserve a better explanation.
The aim is to share knowledge, and that people who are studying, preparing for interviews, or just practicing, can become better at solving problems. Please feel free to comment if you have a suggestion or a different approach!
Problem statement
In a given grid, each cell can have one of three values:
the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) 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 instead.
You can see the examples and more information on the leetcode problem page.
Solution
Always try to solve the problems yourself instead of looking at the solutions on leetcode or the web. Once you see the answer, you tend to thing that those solutions are the only approach to solve the problem and you stop thinking about other possible solutions. For instance, most of the solutions I've seen use BFS, which seems like a good choice given the idea of "time", and you simulate the time passing and rotting the oranges.
However, looking at the grid, I came up with a different approach using DFS, which seems to be faster(100%) than the other proposed solutions(around 80%).
Main idea
If you look at the grid of oranges, you realize that the time it takes for a fresh orange to rotten is the minimum distance from any rotten orange to that fresh orange. Basically, one movement in the grid, whether it is vertical or horizontal, counts as 1 minute.
In general terms you need to do the following:
For each fresh orange you need to find the minimum distance to a rotten orange among all the rotten oranges.
Once you set the minimum distance of all fresh oranges, you go through all the minimum distances and pick the maximum among all of them. This is because the largest distance will dictate the minimum time it will take to rotten.
For instance, if you have the following minimum times/distances:
{12,54,23,21}
The maximum of them is 54. This means that it will take 54 minutes to rotten all the oranges. If we would pick the minimum, which is 12, then after 12 minutes, only that orange would be rotten, but rest are not!. That is why we must take the largest of those values to make sure all of the oranges will be rotten by that time. So by minute 54, we are sure all the oranges are rotten.
Rather than creating a map or some other data structure, we can just reuse the current grid to set the distance/time to each fresh orange. So each grid cell will contain the minimum distance to a rotten orange(only if it is fresh).
For the solution I used a functional approach, in the sense that I divided the solution into method(functions), where each function does one specific thing. Always try to code this way!
As the solution is a bit large, I am gonna split the code in several parts, explaining each part and then show the whole solution.
The main method
private static final int FRESH = 1;
private static final int ROTTEN = 2;
public static final int TIME_OFFSET = 3;
public static final int CANNOT_BE_ROTTEN = -1;
public int orangesRotting(int[][] grid) {
setMinTimeToRotten(grid);
int maxTime = getMaxTimeToRotten(grid);
if (maxTime == CANNOT_BE_ROTTEN) return CANNOT_BE_ROTTEN;
return Math.max(0, maxTime - TIME_OFFSET);
}
}
First we set the minimum time to rotten all the fresh oranges, with the "setMinTimeToRotten" method.
Then we get the max time to rotten among all the minimum times.
Finally we return the result based on the maxTime found. I used an offset here that I will explain in detail with the "setMinTimeToRotten" method.
setMinTimeToRotten method
private void setMinTimeToRotten(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == ROTTEN) {
dfsInAllDirections(grid, i, j, 1 + TIME_OFFSET);
}
}
}
}
This is just the nested for loop to go through the whole grid. The important part happens whenever we find a ROTTEN orange. In that case we do a DFS (Depth First Search), with the Offset. The "dfsInAllDirections" method is just a helper method that goes into all possible directions, horizontally and vertically.
dfs method
private void dfs(int[][] grid, int i, int j, int time) {
if (!isValid(grid, i, j) || !isFresh(grid[i][j])) return;
int originalOrangeValue = grid[i][j];
grid[i][j] = -1;
dfsInAllDirections(grid, i, j, time + 1);
grid[i][j] = getMinTimeToRotten(time, originalOrangeValue);
}
This is the most important method, and where all the logic occurs.
First we check that the grid position, defined by i and j, is valid, meaning it is within the limits of the grid. Then we also need check that the position at grid[i][j] is fresh. If it is not a fresh orange, then we cannot do anything, we are only looking for fresh oranges.
Once we pass this check, we know for sure that we have a fresh orange at position grid[i][j]. So we need to update the distance of this fresh orange. And here is the reason we need an offset.
Because we are reusing the same grid and we are updating the values of each grid, we need to be careful with its value. For instance:
The initial value of a fresh orange will be: "1"
If we update the value with the new distance, let's say "2", then the value of that grid will be "2". This can be confused with a "rotten orange". So in order to avoid this problem we set an offset, so we start with a value of that offset. I set it to "3" for my solution. This means that fresh oranges will be updates with values greater than 3.
But before we set the value for this grid, we need to "mark it" somehow so we don't pass again through the same grid position when doing the DFS. That is why the grid is set to -1.
Then we do again the DFS, from that grid position to search for all possible reachable fresh oranges. Every DFS, we add the "time + 1", meaning it is 1 step further from the original rotten orange that started the initial DFS.
Once we come back from the DFS at that position, we update the value with min value between the old value at that position and the new distance/time.
So basically we are comparing if there is a shorter path from another rotten orange to this fresh orange.
And that's it. Once we go through the whole grid, we have updated the fresh oranges with values that represent the distance/time to rotten the oranges. We just need to pick the maximum of all of those times to get the answer.
Just one thing, we have to be careful to remove the offset that we added, as that offset was just added to avoid the semantics of the values in the grid.
Here is the full solution:
private static final int FRESH = 1;
private static final int ROTTEN = 2;
public static final int TIME_OFFSET = 3;
public static final int CANNOT_BE_ROTTEN = -1;
public int orangesRotting(int[][] grid) {
setMinTimeToRotten(grid);
int maxTime = getMaxTimeToRotten(grid);
if (maxTime == CANNOT_BE_ROTTEN) return CANNOT_BE_ROTTEN;
return Math.max(0, maxTime - TIME_OFFSET);
}
private void setMinTimeToRotten(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == ROTTEN) {
dfsInAllDirections(grid, i, j, 1 + TIME_OFFSET);
}
}
}
}
private int getMaxTimeToRotten(int[][] grid) {
int maxTime = 0;
for (int[] rows : grid) {
for (int value : rows) {
if (value == FRESH) return CANNOT_BE_ROTTEN;
maxTime = Math.max(value, maxTime);
}
}
return maxTime;
}
private void dfsInAllDirections(int[][] grid, int i, int j, int time) {
dfs(grid, i + 1, j, time);
dfs(grid, i - 1, j, time);
dfs(grid, i, j + 1, time);
dfs(grid, i, j - 1, time);
}
private void dfs(int[][] grid, int i, int j, int time) {
if (!isValid(grid, i, j) || !isFresh(grid[i][j])) return;
int originalOrangeValue = grid[i][j];
grid[i][j] = -1;
dfsInAllDirections(grid, i, j, time + 1);
grid[i][j] = getMinTimeToRotten(time, originalOrangeValue);
}
private int getMinTimeToRotten(int time, int originalOrange) {
return originalOrange == FRESH
? time
: Math.min(originalOrange, time);
}
private boolean isFresh(int orange) {
return orange == FRESH || orange > ROTTEN;
}
private boolean isValid(int[][] grid, int i, int j) {
return i >= 0 && i < grid.length && j >= 0 && j < grid[i].length;
}
Complexity
Well this is where it gets complicated. I am not sure about this analysis, so please feel free to comment if you have a better way to understand the complexity.
The key points are:
For each rotten orange, you have to calculate the distance to all reachable fresh oranges.
For simplicity let's think of a square matrix: n = m*m
n : total size of the grid
The worst case would be when we have n/2 rotten oranges and n/2 fresh oranges. Together they fill the whole grid.
This means that we would have the following:
n/2 * n/2 = 1/4 * n^2
This means: For each rotten orange(n/2) we have to calculate the distance to all fresh orange(n/2).
This would give a time complexity:
Time: O(n^2) :
Space: O(1), we are reusing the same grid and no other data structures are required.
Final comments:
I am still thinking about the complexity of the BFS, which seems that should be faster, but the submission in only 82%.
However, my DFS solution is 100%! Not sure if my complexity analysis is correct, and what/how the complexity of the BFS is.
As always try to think of different solutions. I haven't seen anyone using DFS, so I thought I would share my solution :)
Top comments (0)