LeetCode Daily: Count Sub Islands Solution in Java | August 28, 2024

🔍 LeetCode Problem of the Day: Count Sub Islands

Today, we're solving the "Count Sub Islands" problem in Java as part of the LeetCode daily challenge. This problem involves finding and counting sub-islands in a grid using Depth-First Search (DFS).

👉 Solution: Pinned on the comments

🌟 Problem Description:
Given two grids, grid1 and grid2, our goal is to count the number of islands in grid2 that are also present in grid1. An island in grid2 is considered a sub-island if all the land in the island exists in the corresponding positions in grid1.

🔑 Key Points:
DFS Traversal: The problem is approached by performing DFS on each land cell in grid2 to determine if it's a sub-island.
Sub-Island Validation: During the DFS, each cell of the island is checked against grid1. If any part of the island in grid2 is not present in grid1, it's not considered a sub-island.
Edge Cases: The algorithm takes care of out-of-bounds checks and ensures that only connected land cells are considered part of an island.
📝 Code Explanation:
Count Islands: The countSubIslands method iterates over all the cells in grid2. When a land cell is found, DFS is initiated to check if it forms a sub-island.
DFS Implementation: The dfs method is used to explore the entire island. It marks cells as visited and ensures that the island in grid2 is a valid sub-island.
Result: The count of valid sub-islands is returned as the result.

📅 Daily Solutions:
I'm posting solutions to LeetCode daily problems every day. Stay tuned by subscribing and don't forget to hit the bell icon!

👥 Join the Community:
Discuss your solutions in the comments.
Engage with other coders and improve your problem-solving skills.
If this video helped you, please like, share, and subscribe for more daily LeetCode solutions!

#LeetCode #Coding #Programming #TechInterview #GraphAlgorithms #DailyChallenge #Java

[AlgoXploration]

Code: class Solution {
public int countSubIslands(int[][] grid1, int[][] grid2) {
int m = grid1.length;
int n = grid1[0].length;
int count = 0;

for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
//If we find a 1 in grid 2, we need to check
//if it's a sub island
if(grid2[i][j] == 1) {
if(dfs(grid1, grid2, i, j))
count++;
}
}
}

return count;
}

public boolean dfs(int[][] grid1, int[][] grid2, int i, int j) {
int m = grid1.length;
int n = grid1[0].length;

//If out of bounds or water in grid2, return true
if(i < 0 || i >= m || j < 0 || j >= n ||
grid2[i][j] == 0)
return true;

//Mark this cell as visited in grid 2
grid2[i][j] = 0;

//Check if this cell is not part of grid1's island
boolean isSubIsland = grid1[i][j] == 1;

//Visit all 4 neighbouring cells
isSubIsland &= dfs(grid1, grid2, i-1, j);
isSubIsland &= dfs(grid1, grid2, i+1, j);
isSubIsland &= dfs(grid1, grid2, i, j-1);
isSubIsland &= dfs(grid1, grid2, i, j+1);
return isSubIsland;
}
}