It is Thursday July 01, 2021 in the Twin Cities of Minneapolis and St. Paul. The forecast called for a sunny day but clouds have rolled in and out. Hopefully it will not rain.
After having breakfast, my wife and I went out on our daily walk. We run into several people we know. Perhaps people want to get in their workout before heading out for the long weekend. The fourth of July falls this Sunday, so the observed Independence Day (United States) is Monday July 05, 2021.
We do not have plans for the holiday. We will stick to our daily routine. I will try to get in one or two work-blocks each day in addition to do groceries and visit the Farmers Market in St. Paul. For one reason or another this year we have not shopped there yet.
In this post we will solve a very interesting problem involving islands on a 2D grid. LeetCode has several problems involving islands. I believe I have solved a few in this blog. The problem in question is LeetCode 1905 Count Sub Islands.
You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells. An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2. Return the number of islands in grid2 that are considered sub-islands. Constraints: o m == grid1.length == grid2.length o n == grid1[i].length == grid2[i].length o 1 <= m, n <= 500 o grid1[i][j] and grid2[i][j] are either 0 or 1.
We are given two 2D matrices. Our task is to count the number of sub-islands in grid2. In my opinion, this is a simple but challenging task.
public int countSubIslands(int[][] grid1, int[][] grid2) {
}
We will be attempting to solve this problem using the Java programming language and the VSCode IDE on a Windows computer. You may use different resources. In general it is simpler to use the on-line IDE provided by LeetCode. That way you will not be required to develop a test scaffold.
The signature for the function in question requires as arguments the two grids specified in the requirements of the problem.
5,5 1,1,1,0,0 0,1,1,1,1 0,0,0,0,0 1,0,0,0,0 1,1,0,1,1 1,1,1,0,0 0,0,1,1,1 0,1,0,0,0 1,0,1,1,0 0,1,0,1,0 main <<< m: 5 n: 5 main <<< grid1: [1, 1, 1, 0, 0] [0, 1, 1, 1, 1] [0, 0, 0, 0, 0] [1, 0, 0, 0, 0] [1, 1, 0, 1, 1] main <<< grid2: [1, 1, 1, 0, 0] [0, 0, 1, 1, 1] [0, 1, 0, 0, 0] [1, 0, 1, 1, 0] [0, 1, 0, 1, 0] <<< (0,0) count: 1 <<< (2,1) count: 1 <<< (3,0) count: 2 <<< (3,2) count: 2 <<< (4,1) count: 3 <<< g1: [1, 1, 1, 0, 0] [0, 1, 1, 1, 1] [0, 0, 0, 0, 0] [1, 0, 0, 0, 0] [1, 1, 0, 1, 1] <<< g2: [2, 2, 2, 0, 0] [0, 0, 2, 2, 2] [0, 2, 0, 0, 0] [2, 0, 2, 2, 0] [0, 2, 0, 2, 0] main <<< sub-islands: 3 5,5 1,0,1,0,1 1,1,1,1,1 0,0,0,0,0 1,1,1,1,1 1,0,1,0,1 0,0,0,0,0 1,1,1,1,1 0,1,0,1,0 0,1,0,1,0 1,0,0,0,1 main <<< m: 5 n: 5 main <<< grid1: [1, 0, 1, 0, 1] [1, 1, 1, 1, 1] [0, 0, 0, 0, 0] [1, 1, 1, 1, 1] [1, 0, 1, 0, 1] main <<< grid2: [0, 0, 0, 0, 0] [1, 1, 1, 1, 1] [0, 1, 0, 1, 0] [0, 1, 0, 1, 0] [1, 0, 0, 0, 1] <<< (1,0) count: 0 <<< (4,0) count: 1 <<< (4,4) count: 2 <<< g1: [1, 0, 1, 0, 1] [1, 1, 1, 1, 1] [0, 0, 0, 0, 0] [1, 1, 1, 1, 1] [1, 0, 1, 0, 1] <<< g2: [0, 0, 0, 0, 0] [2, 2, 2, 2, 2] [0, 2, 0, 2, 0] [0, 2, 0, 2, 0] [2, 0, 0, 0, 2] main <<< sub-islands: 2
The first input line specifies the dimensions of the two grids. In both test cases we will be using 5×5 grids.
The following input lines describe the rows of the two grids. The rows for grid1 come first followed by the rows for grid2.
Our test code seems to display the number of rows followed by the number of columns.
The contents of grid1 are displayed followed by the contents of grid2.
The following lines display the position of a cell in an island followed by a count. It seems that the first match or sub-island was detected at coordinates (0, 0). The second sub-island was detected at coordinates (3, 0) and the third and last sub-island was detected at coordinates (4, 1). Please take a few moments to map the sub-islands in grid2 to the islands in grid1 and verify that the results so far make sense. I will wait…
…OK, let’s move forward.
Our code seems to display the contents of gri1 followed by the contents of grid2. Note that grid1 has not been disturbed. In grid2 the values for the cells have been changed from 1 to 2. This was probably done to make sure each cell was processed just once. This will become clear when we look at the actual code.
The last line of the test case displays the number of sub-islands found. For additional information and clarification, please refer to the problem definition. LeetCode has provided colorful grids.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
int m = 0;
int n = 0;
int[][] grid1 = null;
int[][] grid2 = null;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read m & n ****
String[] mn = br.readLine().trim().split(",");
m = Integer.parseInt(mn[1]);
n = Integer.parseInt(mn[0]);
// **** read grid 1 ****
grid1 = new int[m][n];
for (int i = 0; i < m; i++) {
int[] row = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
grid1[i] = row;
}
// **** read grid 2 ****
grid2 = new int[m][n];
for (int i = 0; i < grid1.length; i++) {
int[] row = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
grid2[i] = row;
}
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< m: " + m + " n: " + n);
System.out.println("main <<< grid1:"); displayGrid(grid1);
System.out.println("main <<< grid2:"); displayGrid(grid2);
// **** call function of interest and display result ****
// System.out.println("main <<< sub-islands: " + countSubIslands0(grid1, grid2));
// **** call function of interest and display result ****
System.out.println("main <<< sub-islands: " + countSubIslands(grid1, grid2));
}
This is the test code that we wrote to collect the input data, call the function in questions and display the result. Please note that this IS NOT PART OF THE SOLUTION.
I am not going to say much because the descriptions of the test case seem to match closely the test code. Note that we have implemented two solutions. The first has been commented out. We will not go deep into the associated functions since as you will be able to see in the comments section of the code, the function passes the tests but could be optimized.
The code has been left commented out, because both implementations change the input grids. If you wish to run the first implementation, comment out the second. If you do not, the results will be incorrect.
/**
* Display grid.
* Utility function.
* NOT PART OF THE SOLUTION
*/
static void displayGrid(int[][] grid) {
for (int r = 0; r < grid.length; r++) {
System.out.println(Arrays.toString(grid[r]));
}
}
This is a utility function. We use it to display the contents of the grids.
// **** global variables (for ease of use) ****
static int n;
static int m;
static int[][] g1;
static int[][] g2;
static boolean valid = false;
We will be using in both approaches a set of global variables. We could avoid them by passing additional arguments to the different functions. The `valid` variable is only used in the first implementation.
/**
* You are given two m x n binary matrices grid1 and grid2
* containing only 0's (representing water) and 1's (representing land).
* An island is a group of 1's connected 4-directionally (horizontal or vertical).
* Any cells outside of the grid are considered water cells.
*
* An island in grid2 is considered a sub-island
* if there is an island in grid1 that contains all the cells that make up this island in grid2.
*
* Return the number of islands in grid2 that are considered sub-islands.
*
* Runtime: 33 ms, faster than 51.53% of Java online submissions.
* Memory Usage: 75.7 MB, less than 81.59% of Java online submissions.
*/
static int countSubIslands0(int[][] grid1, int[][] grid2) {
// **** initialization ****
int count = 0;
int color = 2; // island color
// **** for ease of use ****
n = grid1.length; // # of rows
m = grid1[0].length; // # of columns
g1 = grid1;
g2 = grid2;
// **** color island(s) in grid1 O(n * m) ****
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
if (grid1[r] == 1)
colorIsland(r, c, color++);
}
}
// **** traverse the grids O(n * m) ****
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
// **** ****
if (g1[r] != 0 && g2[r] == 1) {
// **** valid sub-island ****
valid = true;
// **** clear island from grid2 ****
clearIsland(r, c, g1[r]);
// **** increment sub-island count (if needed) ****
if (valid) count++;
}
}
}
// **** return sub-island count ****
return count;
}
The comment shows the performance of the function. It seems that we should be able to generate a simpler and faster implementation. Due to this fact, we will briefly touch this implementation. In this implementation we touch both grids. Not only that, we perform two different DFS traversals, one on each grid. We start by performing some initializations. We loop through the first grid and color each island with different values. Since the grid starts by implementing all islands with a value of 1, we start by setting the land cell(s) in the first island with 2 and incrementing it on successive islands. The second loop looks for the first cell in an island in grid1 that matches land in the second grid. We flag that we have found a valid sub-island so we need to change the color of the sub-island in grid2 so we do not process the same cells more than once. We then increment the count of sub-islands. When all is said and done, we return the number of sub-islands found in grid2.
/**
* Check if cell (r,c) is in bounds (inside the grid).
* Utility function.
*/
static boolean inBounds(int r, int c) {
return (r >= 0 && r < n && c >= 0 && c < m);
}
This function is used to determine if the coordinates of a cell are inside the grids. We could have saved the use of the function call by just writing the code in-line.
/**
* Color the island starting at the specifed cell in grid1
* with the specified color.
*/
static void colorIsland(int r, int c, int color) {
// **** sanity check(s) ****
if (inBounds(r, c) == false || g1[r] != 1) return;
// **** cell belongs to island with specified color ****
g1[r] = color;
// **** recursively color all adjacent cells with specified color ****
colorIsland(r + 1, c, color); // recurse down
colorIsland(r - 1, c, color); // recurse up
colorIsland(r, c + 1, color); // recurse right
colorIsland(r, c - 1, color); // recurse left
}
This function is used to color each island with the specified color. This is needed to check that we are processing a single island at a time. Note that it implements a DFS approach.
/**
* Remove (change to water) from grid2 the specified island
* starting at the specified cell.
*/
static void clearIsland(int r, int c, int color) {
// **** sanity check(s) ****
if (inBounds(r, c) == false || g2[r] == 0) return;
// **** check if cell not in island in grid1 ****
if (g1[r] != color)
valid = false;
// **** flag this cell as being processed (mark it as water) ****
g2[r] = 0;
// **** check adjacent cells recursively ****
clearIsland(r + 1, c, color); // recurse down
clearIsland(r - 1, c, color); // recurse up
clearIsland(r, c + 1, color); // recurse right
clearIsland(r, c - 1, color); // recurse left
}
This function is used to change back to `water` the cells of an island that we have processed. This function also implements a DFS approach.
So let’s see if we can operate on a single grid. That should shave some execution time.
/**
* You are given two m x n binary matrices grid1 and grid2
* containing only 0's (representing water) and 1's (representing land).
* An island is a group of 1's connected 4-directionally (horizontal or vertical).
* Any cells outside of the grid are considered water cells.
*
* An island in grid2 is considered a sub-island
* if there is an island in grid1 that contains all the cells that make up this island in grid2.
*
* Return the number of islands in grid2 that are considered sub-islands.
*
* Runtime: 17 ms, faster than 98.51% of Java online submissions.
* Memory Usage: 76.6 MB, less than 80.59% of Java online submissions.
*/
static int countSubIslands(int[][] grid1, int[][] grid2) {
// **** for ease of use ****
n = grid1.length; // # of rows
m = grid1[0].length; // # of columns
g1 = grid1;
g2 = grid2;
// **** initialization ****
int count = 0;
// **** DFS on each cell in grid2 (if on land) O(m * n) ****
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
// **** unvisited land in g2 ****
if (g2[r] == 1) {
// **** increment count (if island in g1) ****
count += dfs(r, c);
// ???? ????
System.out.println("<<< (" + r + "," + c + ") count: " + count);
}
}
}
// ???? ????
System.out.println("<<< g1:"); displayGrid(g1);
System.out.println("<<< g2:"); displayGrid(g2);
// **** return count of sub-islands ****
return count;
}
We start by setting some variables.
We now enter a loop in which we are looking for a cell in an island in grid2. When found, we increment the sub-island count by traversing all the cells in the sub-island.
When all is done, the count represents the number of found sub-islands.
/**
* DFS approach.
*/
static int dfs(int r, int c) {
// **** base case(s) ****
if (r < 0 || c < 0 || r >= n || c >= m || g2[r] == 2) return 1;
if (g2[r] == 0) return 1;
// **** set this cell to 2 (was 1) ****
g2[r] = 2;
// **** recursive calls in four directions (if g1 cell is part of an island) ****
return g1[r] // land on g1
& dfs(r + 1, c) // recursive call down
& dfs(r - 1, c) // recursive call up
& dfs(r, c + 1) // recursive call right
& dfs(r, c - 1); // recursive call left
}
This recursive call implements the DFS algorithm. We start by testing a couple of end cases. Note that both return a value of 1.
We then set the value for the cell to 2 so we avoid visiting the same cell multiple times.
Finally we check the corresponding cell in grid1 and perform a set of recursive calls in each direction. When done, each sub-island will have cells of value 2.
Please take a look at the initial and final contents of the grid2. The values in grid1 have not been altered.
Also note the execution time of this approach. You can find it in the comments section of the second implementation.
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, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John