While generating this post in WordPress I noticed that we have now more than 3000 subscribers. Thanks you very much! If you have specific problems please let me know so I can try to solve them here.
I do not use Facebook but my wife does. Earlier today during my first break of the day, she was telling me about a few posts / news regarding the past debates between President Donald Trump and Joe Biden and the one between Vice President Mike Pence and Kamala Harris. I am no longer sure what the points of debates are. Allow me to explain.
Many years ago every Sunday at 06:00 PM my wife and I would turn on our TV set to watch 60 Minutes. The anchors of the show and correspondents have change with time. The program used to be objective. With time that has changed.
In one of the episodes there was a very good segment that addressed a change 
in politics and news in general. What started to happen a few years before was that politicians and news people were socially mixing and mingling. Their kids were attending the same schools and the parents were attending the same social events. The expected problem was that politicians and news people were going to work as a unit. A few years after we have experience exactly what was described in that episode.
In a few weeks Election Day will be upon us. My wife and I will go that day to the polls to vote. A large number of people have received multiple ballots which have been filled returned via USPS. Not sure what will happen after the votes are tallied. In my humble opinion, the Supreme Court should cancel elections this coming month. They should require all people to register and get a voter ID card. Every registered voter should vote once on Election Day 2021. If you cannot make it to the polls, you do not vote. If Donald Trump wins the 2021 elections, then he would just server three more years; otherwise the newly lawfully elected president will server four years. Our electoral system, among many other things, is in shambles. We need to clean up and move forward.
By the way, my wife and I no longer watch TV. There are few (if any) programs that are worth the time. I rather spend it chatting, reading or watching a movie on a paid service.
Now let’s get to the subject of this post. I found LeetCode problem 994 “Rotting Oranges”. Read the requirements and decided to give it a try. My first thoughts were that the problem was somewhat similar to Number of Islands which I solved a week or so ago. This problem is more complicated. Not sure if it is possible to solve it in about 45 minutes (average interview time) unless you have worked the problem before and are able to recall the solution. As we will see shortly, there are a lot of details, but more important is to have an overall approach.
The approach I took is based on Breadth First Search. As usual, if you feel inclined to give this problem a try, read the description and examples and determine an approach. If you get stuck, try getting enough info and then continue solving the problem.
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. Note: 1 <= grid.length <= 10 1 <= grid[0].length <= 10 grid[i][j] is only 0, 1, or 2.
In a nutshell, we are given a grid of no more than 10 x 10 cells. Will discuss later some future implications and how to address them. Each cell may be empty, hold a fresh or a rotten orange. The problem describes how adjacent fresh oranges rot. The idea is to determine how long it will take for all the oranges in the grid to go bad or determine if not all oranges will go bad.
The provided examples illustrate what happens with time. It also contains an example in which one orange will not rot.
I will write a test scaffolding and generate a solution using the Java programming language. I will solve the problem on one of my Windows 10 computers using the VSCode IDE. Note that the test scaffolding is not part of the solution.
class Solution {
public int orangesRotting(int[][] grid) {
}
}
This is the function we need to implement. The only argument is the grid or oranges. The values can be 0, 1 or 2.
3 2,1,1 1,1,0 0,1,1 main <<< R: 3 main <<< grid: [2, 1, 1] [1, 1, 0] [0, 1, 1] main <<< orangesRotting0: 4 main <<< orangesRotting: 4 3 2,1,1 0,1,1 1,0,1 main <<< R: 3 main <<< grid: [2, 1, 1] [0, 1, 1] [1, 0, 1] main <<< orangesRotting0: -1 main <<< orangesRotting: -1 1 0,2 main <<< R: 1 main <<< grid: [0, 2] main <<< orangesRotting0: 0 main <<< orangesRotting: 0
I decided to provide the number of rows for the grid. Following are individual lines with data for each cell in a row. The test scaffolding displays the number of rows followed by the contents of the grid. This is done to verify if all is well so far.
The software then makes two calls and shows the associated results. They both seem to match. I used a single BFS approach. The difference between them is some optimization that I used on the second pass. What is interesting to note, that the same solution submitted at different times would take more or less time. I should have timed my code. Perhaps I will start doing so in future posts.
/**
* Test scaffolding.
* NOT PART OF SOLUTION
*/
public static void main(String[] args) {
// **** open the scanner ****
Scanner sc = new Scanner(System.in);
// **** read the number of rows ****
int R = Integer.parseInt(sc.nextLine());
// ???? ????
System.out.println("main <<< R: " + R);
// **** ****
int[][] grid = new int[R][];
// **** loop reading the rows for the grid ****
for (int r = 0; r < R; r++) {
// **** read the next row of data ****
String[] dataRow = sc.nextLine().split(",");
// **** create the grid row for this data ****
grid[r] = new int[dataRow.length];
// **** populate the grid row ****
for (int c = 0; c < dataRow.length; c++) {
grid[r] = Integer.parseInt(dataRow);
}
}
// **** close the scanner ****
sc.close();
// ???? ????
System.out.println("main <<< grid:");
for (int r = 0; r < R; r++)
System.out.println(Arrays.toString(grid[r]));
// **** compute and display the result ****
System.out.println("main <<< orangesRotting0: " + orangesRotting0(grid));
// **** compute and display the result ****
System.out.println("main <<< orangesRotting: " + orangesRotting(grid));
}
Not much to say about the test scaffolding. Based on the screen capture and the description there is little left to the imagination.
I would like to note the operation of the loop. We read a string of integers followed by ‘,’s. We split the line in order to extract a set of strings representing integer values. To populate a row, we convert the strings to integers and assign them to cells in the grid. Note that in our examples, the values are single digit. The same set of steps would work if the integer values would have multiple digits.
/**
* 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.
*
* Runtime: 12 ms, faster than 7.62% of Java online submissions.
* Memory Usage: 38.7 MB, less than 91.13% of Java online submissions.
*/
static int orangesRotting0(int[][] grid) {
// **** initialization (fresh and rotten oranges) ****
HashSet<String> fresh = new HashSet<String>();
HashSet<String> rotten = new HashSet<String>();
// **** populate hash sets with grid coordinates ****
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[r].length; c++) {
if (grid[r] == 1)
fresh.add("" + r + c);
else if (grid[r] == 2)
rotten.add("" + r + c);
}
}
// **** initialize time ****
int min = 0;
// **** loop infecting oranges while we have fresh ones ****
while (fresh.size() != 0) {
// **** oranges that will get infected in this pass ****
HashSet<String> infected = new HashSet<String>();
// **** traverse all infected oranges ****
for (String rot : rotten) {
// **** extract grid coordinates ****
int r = rot.charAt(0) - '0';
int c = rot.charAt(1) - '0';
// **** infect adjacent oranges ****
infected = infectAdjacent0(grid, r, c, fresh, infected);
}
// **** did not infect new oranges ****
if (infected.size() == 0) {
return -1;
}
// **** only consider the last infected oranges ****
rotten = infected;
// **** increment time ****
min++;
}
// **** return time ****
return min;
}
After several attempts it became obvious that we need to keep track of the fresh and the rotten oranges. The fresh set will help us detect isolated oranges that will not rot. In addition we will be able to detect (like in example # 2) if we only have rotted oranges and there is little we need to do except to return a 0.
The loop traverses the grid. So far this is O(n) execution. We populate the sets of fresh and rotten oranges. Note that the values represent a string with two digits. The first digit is the row number [0-9] and the second digit column number [0- 9]. In other words each orange will be represented with a unique string of two digits associated with the address of the cell in the grid.
We then set the time to zero. After each loop (representing a minute) some oranges may be infected and rot. In the Number of Islands problem we just needed to count the number of islands. A simple traversal that covers all the connected oranges would not suffice because we need to determine what happens after each minute, not the final result.
We now enter a while loop (similar to BFS) in which we visit all the initially rotten oranges. We then extract the row and column location of the rotten orange. Note that if the grid would be larger than 10 x 10, we could as easily separate the row and column with a ‘,’. To extract the values we would split the string and convert the strings to integer similar to what we have done in the test scaffolding and in many other problems.
We then make a call to the infectedAdjacent() function to get the list of fresh oranges that would be compromised by the current rotten orange. We will visit the function in question in a few. At this time we need to understand that we pass the grid with the coordinates of a rotten orange, the sets of fresh and infected oranges. Note that the set of infected oranges was initialized as empty. We return the set of infected oranges by each rotted orange as expressed by the for() loop.
After the for() loop we check if we did not infect an orange and return a -1 indicating that not all fresh oranges can be infected. We do this because when we enter the for() loop we had fresh oranges. If we did not infect any fresh orange, the remaining fresh orange(s) cannot be reached.
At this point we have used the initial set of infected oranges to infect a new set. We point to the new set of infected oranges and used them as the base of rotten oranges to infect new ones. That is it with the single exception that we need to increment the time because the first loop has been completed.
When done we just return the number of minutes / loops that it took to infect all the fresh oranges.
Hope you can see the parallel of this approach with the BFS search. In this case we do not use a queue, but the approach is similar.
/**
* Infect adjacent oranges.
*/
static HashSet<String> infectAdjacent0(int[][] grid, int r, int c, HashSet<String> fresh, HashSet<String> infected) {
// **** loop once per direction (up, right, down and left) ****
for (int i = 0; i < 4; i++) {
// **** ****
String coords = "";
// **** infect up orange (if needed) ****
if (i == 0 && r > 0 && grid[r - 1] == 1) {
coords = "" + (r - 1) + c;
}
// **** infect right orange ****
if (i == 1 && c < grid[r].length - 1 && grid[r] == 1) {
coords = "" + r + (c + 1);
}
// **** infect down orange ****
if (i == 2 && r < grid.length - 1 && grid[r + 1] == 1) {
coords = "" + (r + 1) + c;
}
// **** infect left orange ****
if (i == 3 && c > 0 && grid[r] == 1) {
coords = "" + r + (c - 1);
}
// **** skip this direction ****
if (coords == "")
continue;
// **** move orange (if needed) ****
if (fresh.contains(coords)) {
// **** remove orange from the fresh set ****
fresh.remove(coords);
// **** add orange to the infected set ****
infected.add(coords);
}
}
// **** return set of infected oranges ****
return infected;
}
This is the function that we use to determine if we have adjacent fresh oranges that we can infect in the four possible relative locations (up, right, down and left). We visit each direction in the loop. For each direction we determine if we can get to the adjacent position and if so, if it contains a fresh orange. If that is the case we generate the grid coordinate of the infected orange.
We now check if the coordinates are blank, signaling that for the current direction we could not locate an orange. If we located a fresh orange, then we remove it from the set of fresh oranges and insert it in the set of infected oranges.
When all is set and done, we return the set of infected oranges surrounding the specified rotten orange.
As we already know, we repeat the call or the rest of the remaining rotten oranges to end up with a list of all infected oranges by the current set of rotten oranges. With all this talk of oranges, I am starting to get thirsty for some orange juice!
// **** grid directions (up, right, down and left) ****
static final int[][] dirs = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
This is something I learned to encapsulate and simplify visiting the adjacent cells of a cell. In this case we have four directions. We did not include diagonals. Other problems may only use diagonals or all eight directions.
/**
* Infect grid adjacent oranges.
*/
static HashSet<String> infectAdjacent(int[][] grid, int r, int c, HashSet<String> fresh, HashSet<String> infected) {
// **** loop once per direction (up, right, down and left) ****
for (int[] dir : dirs) {
// **** ****
String coords = "" + (r + dir[0]) + (c + dir[1]);
// **** move current orange (if needed) ****
if (fresh.contains(coords)) {
// **** remove orange from the fresh set ****
fresh.remove(coords);
// **** add orange to the infected set ****
infected.add(coords);
}
}
// **** return set of infected oranges ****
return infected;
}
This version of the infectedAdjacent() function makes use of the array of directions. As you can see the number of lines in the function has been reduced, yet the implementation is easy to follow. That said; I decided to eliminate this function completely. I just left it as a reference.
/**
* 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.
*
* Runtime: 10 ms, faster than 9.22% of Java online submissions.
* Memory Usage: 38.9 MB, less than 70.31% of Java online submissions.
*/
static int orangesRotting(int[][] grid) {
// **** initialization (fresh and rotten oranges) ****
HashSet<String> fresh = new HashSet<String>();
HashSet<String> rotten = new HashSet<String>();
// **** populate hash sets with grid coordinates ****
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[r].length; c++) {
if (grid[r] == 1)
fresh.add("" + r + c);
else if (grid[r] == 2)
rotten.add("" + r + c);
}
}
// **** initialize time ****
int min = 0;
// **** loop infecting oranges while we have fresh ones ****
while (fresh.size() != 0) {
// **** oranges that will get infected in this pass ****
HashSet<String> infected = new HashSet<String>();
// **** traverse all infected oranges ****
for (String rot : rotten) {
// **** extract grid coordinates ****
int r = rot.charAt(0) - '0';
int c = rot.charAt(1) - '0';
// **** infect adjacent oranges ****
for (int[] dir : dirs) {
// **** ****
String coords = "" + (r + dir[0]) + (c + dir[1]);
// **** move current orange (if needed) ****
if (fresh.contains(coords)) {
// **** remove orange from the fresh set ****
fresh.remove(coords);
// **** add orange to the infected set ****
infected.add(coords);
}
}
}
// **** did not infect new oranges ****
if (infected.size() == 0) {
return -1;
}
// **** only consider the last infected oranges ****
rotten = infected;
// **** increment time ****
min++;
}
// **** return time ****
return min;
}
This implementation is similar to the original one. Instead of making a separate call to collect the infected oranges, we achieve the same result with on-line code.
The inner for() loop is equivalent to the call used to find infected oranges surrounding a specific cell in the grid.
The rest of the code is the same as before.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 3040 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa