Last evening before going to bed, I left a window in the kitchen opened just a crack. The temperature was forecasted to drop down to 37F, so I hopped it was going to be fine.
A few minutes past midnight I woke up. It felt somewhat chilly. I closed the window and checked the temperature in the upper level zone. It was at 68F which is at what we keep it during the winter months. I turned on the heat in the zone and went back to bed. During the rest of the night I heard the furnace kick in a couple times.
During breakfast my wife asked if windows were closed and the furnace was on. I told her about my midnight adventure. We agreed on leaving windows closed from now on until next spring. The system at home has an air exchange unit so it makes sense to keep the windows closed and the temperature at 68F.
For my comments, you can tell that during the COVID-19 pandemic there is 
not much to talk about.
This morning I woke up around 05:00 AM. I received a message from my best friend indicating that he had to work early and to postpone our weekly Skype call for next Friday. I replied to his message. I then spend some time reading the Hacker’s Delight book by Henry Warren. I am enjoying the book. It is interesting to learn to perform manipulations on integers to obtain complex results with very few steps.
I decided to work on LeetCode problem 200 Number of Islands.
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
If interested please visit the LeetCode side, and read the full requirements and examples. The idea is that we are provided with a grid of characters. Each character may take value ‘0’ indicating water, or ‘1’ indicating land. The idea is to count the number of islands that you can find in the grid.
By reading the requirements it became apparent that we will probably need to traverse the grid looking for the cells that are contiguous so we can identify islands. If you are still interested, please give it a try and compare approaches. By trying and looking at others work, we can always learn something new.
I decided to use the Java programming language, the VSCode IDE and a Windows 10 computer. The IDE and the platform should make no difference. As a matter of fact I also run VSCode on Linux machines.
The idea is to complete the following function:
class Solution {
public int numIslands(char[][] grid) {
}
}
I generated my own test scaffolding because I like to solve and experiment while using the essence of the TDD approach.
4,5 "1","1","1","1","0" "1","1","0","1","0" "1","1","0","0","0" "0","0","0","0","0" main <<< grid: [1, 1, 1, 1, 0] [1, 1, 0, 1, 0] [1, 1, 0, 0, 0] [0, 0, 0, 0, 0] main <<< numIslands: 1 main <<< grid: [x, x, x, x, 0] [x, x, 0, x, 0] [x, x, 0, 0, 0] [0, 0, 0, 0, 0] 4,5 "1","1","0","0","0" "1","1","0","0","0" "0","0","1","0","0" "0","0","0","1","1" main <<< grid: [1, 1, 0, 0, 0] [1, 1, 0, 0, 0] [0, 0, 1, 0, 0] [0, 0, 0, 1, 1] main <<< numIslands: 3 main <<< grid: [x, x, 0, 0, 0] [x, x, 0, 0, 0] [0, 0, x, 0, 0] [0, 0, 0, x, x] 2,1 "1" "1" main <<< grid: [1] [1] main <<< numIslands: 1 main <<< grid: [x] [x] 1,7 "1","0","1","1","0","1","1" main <<< grid: [1, 0, 1, 1, 0, 1, 1] main <<< numIslands: 3 main <<< grid: [x, 0, x, x, 0, x, x] 4,5 "1","1","1","1","1" "1","1","1","1","1" "1","1","1","1","1" "1","1","1","1","1" main <<< grid: [1, 1, 1, 1, 1] [1, 1, 1, 1, 1] [1, 1, 1, 1, 1] [1, 1, 1, 1, 1] main <<< numIslands: 1 main <<< grid: [x, x, x, x, x] [x, x, x, x, x] [x, x, x, x, x] [x, x, x, x, x] 5,5 "1","0","0","0","0" "0","0","0","0","1" "1","0","0","0","0" "0","0","0","0","1" "1","0","0","0","0" main <<< grid: [1, 0, 0, 0, 0] [0, 0, 0, 0, 1] [1, 0, 0, 0, 0] [0, 0, 0, 0, 1] [1, 0, 0, 0, 0] main <<< numIslands: 5 main <<< grid: [x, 0, 0, 0, 0] [0, 0, 0, 0, x] [x, 0, 0, 0, 0] [0, 0, 0, 0, x] [x, 0, 0, 0, 0]
I decided to present the data preceded by two numbers. In the aftermath only the number of rows is used by the test scaffolding. The first number represents the number of rows in the grid followed by the number of columns. Each of the following rows of numbers represents a row in the grid.
Based on the screen capture, it seems like we display the contents of the grid after it has been created and populated. I like to make sure things are as expected before processing the data.
The number of islands is displayed. It seems that the numbers match the input data.
After we are done we display the grid a second time. Note that where we had ‘1’s we now have ‘x’s. This is a byproduct used to make sure that when we traverse a graph, we do not get stuck by revisiting visited cells. This is how our solution keeps track of visited cells. The approach will become obvious when we see the actual code.
The two examples offered by LeetCode are covered. I made up some additional tests, and some were picked up when I made a mistake or two while copying and pasting code to while solving and improving my code.
/**
* Test scaffolding
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read line with row and column counts ****
String[] rn = sc.nextLine().split(",");
int R = Integer.parseInt(rn[0]);
// int C = Integer.parseInt(rn[1]);
// **** create an empty grid ****
char[][] grid = new char[R][];
// **** loop reading a row of values at a time ****
for (int r = 0; r < R; r++) {
// **** read the next row of data ****
String data = sc.nextLine();
// **** remove all '"'s ****
data = data.replaceAll("\"", "");
// **** remove all '','s ****
data = data.replaceAll(",", "");
// **** populate this row ****
grid[r] = data.toCharArray();
}
// **** close scanner ****
sc.close();
// ???? ????
System.out.println("main <<< grid:");
for (int r = 0; r < grid.length; r++)
System.out.println(Arrays.toString(grid[r]));
// **** count and display the number of islands ****
System.out.println("main <<< numIslands: " + numIslands(grid));
// ???? ????
System.out.println("main <<< grid:");
for (int r = 0; r < grid.length; r++)
System.out.println(Arrays.toString(grid[r]));
}
My test scaffolding is simple. We start by reading the line with the row and column counts. As I mentioned earlier, the number of columns is not used directly.
We create a grid with the proper number of rows. We then loop reading a line of data at a time. I could have eliminated the double quotes, but I just copied, pasted and made minor editing changes from what was in the LeetCode examples.
After removing unneeded symbols, the data string is used to extract the characters into a character array and put it into our grid.
We then display the completed grid. All seems to be fine.
We then call the function we need to develop, and display the results which should be the total number of islands in the grid.
As we discussed earlier, the final grid is displayed.
/**
* Given a 2d grid map of '1's (land) and '0's (water),
* count the number of islands.
* Runtime: 3 ms, faster than 31.96% of Java online submissions.
* Memory Usage: 44.3 MB, less than 20.73% of Java online submissions.
* Execution O(n * m)
*/
static int numIslands(char[][] grid) {
// **** sanity check(s) ****
if ((grid == null) || (grid.length == 0))
return 0;
// **** initialize variable(s) ****
int num = 0;
// int c = 0;
// // **** loop once per row ****
// for (int r = 0; r < grid.length; r++) {
// // **** loop while an unvisited island ****
// while ((c = new String(grid[r]).indexOf('1')) != -1) {
// // **** visit adjacent cells ****
// visitIsland(grid, r, c);
// // **** count this island ****
// num++;
// }
// }
// **** loop once per row ****
for (int r = 0; r < grid.length; r++) {
// **** loop through each column ****
for (int c = 0; c < grid[r].length; c++) {
// **** visit cell (if on land) ****
if (grid[r] == '1') {
// **** visit adjacent cells ****
visitIsland(grid, r, c);
// **** count this island ****
num++;
}
}
}
// **** return number of islands ****
return num;
}
I have written several million lines of code in C language. C is not as forgiving as other programming languages (i.e., Java). In general, I like to check arguments, allocate resources, perform the task at hand hopefully without introducing side effects, releasing resources and then returning results. I always adhere to such template when working in C, C++ and Java. On scripting languages it is not easy to follow such approach and in most cases not as important.
Note that I commented out a loop. On the commented out one we loop once per row. In the inner loop we loop while there are cells indicating land. If a row does not contain land, then we skip the loop. If we enter the inner loop we make a call to a recursive function which will see in a few. After the recursive function returns, we increment the count of islands.
Not that in the uncommented loop, we loop once per row and once per cell / column in the grid. If the cell indicates land, we then visit it and increment the count of islands. When done we return the total number of islands.
/**
* Visit the entire island.
* Recursive call.
* Execution O(n * m)
*/
static void visitIsland(char[][] grid, int r, int c) {
// **** base condition ****
if (grid[r] == '0' || grid[r] == 'x')
return;
// **** flag as visited ****
grid[r] = 'x';
// **** recurse right ****
if (c < grid[r].length - 1)
visitIsland(grid, r, c + 1);
// **** recurse down ****
if (r < grid.length - 1)
visitIsland(grid, r + 1, c);
// **** recurse left ****
if (c > 0)
visitIsland(grid, r, c - 1);
// **** recurse up ****
if (r > 0)
visitIsland(grid, r - 1, c);
}
The visitIsland() function solves the core of the problem. We only call it when we run into land (cell contents == ‘1’). In the function we check if we have a ‘0’ (indicating water) or an ‘x’ (indicating we have already visit this cell). We could have used ‘0’ but I prefer something different so when done we can clearly identify the islands. This is the recursive base condition.
We then flag the cell as visited. If we do not do so, we can visit it again on a different pass. Such condition might cause the traversal to loop forever.
The next sets of statements, if executed, make recursive calls. As the requirements state, we have to check cells that are above, to the right, bellow and above to determine if the island overlaps. This is a typical way to traverse a graph.
/**
* Return index of '1' in the specified character array.
* Execution O(m)
* !!! NOT USED IN SOLUTION !!!
*/
static int indexOfOne(char[] ca) {
// // **** ****
// String str = new String(ca);
// // **** ****
// int index = str.indexOf('1');
// // **** ****
// return index;
// **** one liner ****
return new String(ca).indexOf('1');
}
This function is no longer use. As you can see the original version generated a string using the specified array of characters. Then we searched for the first ‘1’ in the string and returned the index in the string (or array). This was used to determine if a row contained a ‘1’ (land).
The next version of the function (not commented out) shows the previous 3 statements merged into one.
The reason the function is no longer used, is that the one liner was incorporated directly into the commented out section in the numIslands() function.
That is it. As you can see different versions of the code with different variations were tested in search of best performance. The final version (currently not commented out) is the one that performs as indicated in the comments of the numIslands() function.
The traversal of cells in the grid implements a depth first search approach. This is very common in graph traversal algorithms.
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 2875 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa