We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Sub Islands

Difficulty: Medium

Problem Description

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.

Key Insights

  • An island is defined by connected 1's in a grid.
  • A sub-island in grid2 must entirely exist within an island in grid1.
  • We can use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore and identify islands.
  • We need to check if all cells of an island in grid2 are also 1's in grid1.

Space and Time Complexity

Time Complexity: O(m * n) - We traverse each cell of the grid once. Space Complexity: O(m * n) - The recursion stack or the queue can go as deep as the number of cells in the grid.

Solution

The solution involves using a depth-first search (DFS) algorithm to explore the islands in grid2. For each cell that is part of an island in grid2 (i.e., a 1), we will check if all connected cells (the entire island) are also 1's in grid1. If they are, we increment our sub-island count. We can use a visited matrix or modify grid2 directly to keep track of which cells have been processed.

Code Solutions

def countSubIslands(grid1, grid2):
    def dfs(x, y):
        if x < 0 or x >= len(grid2) or y < 0 or y >= len(grid2[0]):
            return True  # Out of bounds
        if grid2[x][y] == 0:
            return True  # Water cell
        grid2[x][y] = 0  # Mark as visited
        # Check if the cell is part of a sub-island
        is_sub_island = grid1[x][y] == 1
        # Explore all 4 directions
        is_sub_island &= dfs(x + 1, y)
        is_sub_island &= dfs(x - 1, y)
        is_sub_island &= dfs(x, y + 1)
        is_sub_island &= dfs(x, y - 1)
        return is_sub_island

    count = 0
    for i in range(len(grid2)):
        for j in range(len(grid2[0])):
            if grid2[i][j] == 1:  # Found a new island in grid2
                if dfs(i, j):  # Check if it's a sub-island
                    count += 1
    return count
← Back to All Questions