Medium

Count Sub Islands

028

Return the number of islands in grid2 whose land cells are all also land in grid1.

EXAMPLES

Example 1

Input
{
  "grid1": [
    [
      1,
      1,
      1
    ],
    [
      0,
      1,
      0
    ]
  ],
  "grid2": [
    [
      1,
      1,
      0
    ],
    [
      0,
      1,
      1
    ]
  ]
}

Output
0

FUNCTION SHAPE

grid1: intMatrixgrid2: intMatrix→int

SOLUTION NOTE

Very similar to previous problems. DFS on islands in grid2, and check if grid1 is a super-set island. Note that we have to run dfs for all neighbours in grid2, even if we already know grid1[i][j] != 1. This is because we have to mark this whole island in grid2 as invalid, otherwise we will overcount.

Reveal reference solution +

pythonREFERENCE

def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
    dirs = [(0,1),(1,0),(-1,0), (0,-1)]
    m,n = len(grid1), len(grid1[0])
    def dfs(i, j):
        if not (0 <= i < m and 0 <= j < n) or grid2[i][j] != 1: return True
        grid2[i][j] = 0
        return all([dfs(i+x,j+y) for x,y in dirs]) and grid1[i][j] == 1
    return sum(dfs(i,j) for i in range(m) for j in range(n) if grid2[i][j] == 1)

TimeO(m*n)

SpaceO(m*n)

Open on LeetCode ↗