solution-java.md

Intuition

The problem involves determining whether a set of islands in one grid grid2 are sub-islands of corresponding islands in another grid grid1. An island in grid2 is considered a sub-island if all of its land cells 1s are within the bounds of a corresponding island in grid1. My first thought was to utilize a depth-first search (DFS) to explore each island in grid2 and check if it is fully contained within an island in grid1.

Approach

The approach involves iterating over each cell in grid2. When a land cell 1 is encountered, we perform a DFS to check if all the land cells connected to it form a sub-island within grid1. During the DFS, we mark the visited cells in grid2 to avoid revisiting them. If the entire island in grid2 corresponds to land cells in grid1, it is counted as a sub-island. We continue this process until all cells have been checked.

Complexity

• Time complexity: The time complexity is O(m × n), where m is the number of rows and n is the number of columns in the grids. This is because each cell in grid2 is visited at most once during the DFS.

• Space complexity: The space complexity is O(m × n), mainly due to the recursion stack used during the DFS. In the worst case, the stack depth can be equal to the number of cells in the grid.

Code

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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid2[i][j] == 1 && dfs(grid1, grid2, i, j, m, n)) {
                    count++;
                }
            }
        }

        return count;
    }

    private boolean dfs(int[][] grid1, int[][] grid2, int i, int j, int m, int n) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid2[i][j] == 0) {
            return true;
        }

        grid2[i][j] = 0; 
        boolean isSubIsland = grid1[i][j] == 1;

        boolean down = dfs(grid1, grid2, i + 1, j, m, n);
        boolean up = dfs(grid1, grid2, i - 1, j, m, n);
        boolean right = dfs(grid1, grid2, i, j + 1, m, n);
        boolean left = dfs(grid1, grid2, i, j - 1, m, n);

        return isSubIsland && down && up && right && left;
    }
}