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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Sub Islands

Number: 2035

Difficulty: Medium

Paid? No

Companies: DoorDash, X

Problem Description

We are given two m x n binary matrices grid1 and grid2. An island is defined as a group of 1's connected 4-directionally (horizontal or vertical). An island in grid2 is considered a sub-island if every cell in that island is also land (1) in grid1. The task is to count the number of such sub-islands in grid2.

Key Insights

  • Traverse each island in grid2 using DFS or BFS.
  • While traversing, verify each cell belongs to land in grid1.
  • If any cell in the current island of grid2 is water in grid1, the whole island is disqualified.
  • Mark visited cells in grid2 to avoid redundant processing.
  • Process each cell in grid2 only once, leading to an efficient solution.

Space and Time Complexity

Time Complexity: O(m * n) as every cell is visited at most once. Space Complexity: O(m * n) due to recursion/stack space in the worst-case scenario.

Solution

We iterate over grid2 and whenever a cell with value 1 is found, we perform a DFS (or BFS) to scan all connected cells forming the island. During the DFS, we check if each cell in grid2 has a corresponding 1 in grid1. If not, we mark the island as invalid for being a sub-island. After visiting the entire island, if it still qualifies as a sub-island, we increment our count. We use grid2 itself to mark visited cells to avoid extra space.

Code Solutions

def countSubIslands(grid1, grid2):
    rows, cols = len(grid2), len(grid2[0])
    # Directions: up, down, left, right
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    def dfs(r, c):
        nonlocal is_sub_island
        # If corresponding cell in grid1 is water, then mark island invalid.
        if grid1[r][c] == 0:
            is_sub_island = False
        # Mark the cell in grid2 as visited by setting it to 0.
        grid2[r][c] = 0
        # Traverse all four directions.
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid2[nr][nc] == 1:
                dfs(nr, nc)
    
    count = 0
    # Process each cell in grid2.
    for r in range(rows):
        for c in range(cols):
            if grid2[r][c] == 1:
                is_sub_island = True
                dfs(r, c)
                if is_sub_island:
                    count += 1
    return count

# Example usage:
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]]
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]]
print(countSubIslands(grid1, grid2))  # Expected Output: 3
← Back to All Questions