Leetcode Daily Question 28/08/2024 - 1905. Count Sub Islands

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.

Solution: ►

from typing import List
class Solution:
  def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
    count = 0
    rows = len(grid1)
    cols = len(grid1[0])
    
    def dfs(grid1,grid2,i,j,m,n):
      if i < 0 or j < 0 or i >= m or j >= n or grid2[i][j] == 0:
        return True
      
      grid2[i][j] == 0
      isSubIsland = True
      if grid1[i][j] == 0:
        isSubIsland = False
      
      isSubIsland = dfs(grid1,grid2,i+1,j,m,n) and isSubIsland
      isSubIsland = dfs(grid1,grid2,i-1,j,m,n) and isSubIsland
      isSubIsland = dfs(grid1,grid2,i,j+1,m,n) and isSubIsland
      isSubIsland = dfs(grid1,grid2,i,j-1,m,n) and isSubIsland
      
      return isSubIsland
    
    for i in range(rows):
      for j in range(cols):
        if grid2[i][j] == 0:
          if dfs(grid1,grid2,i,j,rows,cols):
            count += 1
                  
            
      return count

Explanation:

We can solve this problem by performing dfs and checking each land cell in islands of grid2 to see if corresponding land cells are in grid1 too.

If both of these are true, then we have found a subisland.

To see this more concretely, we can use an example. Consider the two grids

Here is how our dfs would work. We traverse grid2.

At position (0,0), grid2[0][0] = 1 and grid1[0][0] = 1, so we can continue to search its neighbour.

Moving right to (0,1), grid2[0][1] = 1 and grid1[0][1] = 1, so we still have a valid island.

Moving right again to (0,2), grid2[0][2] = 1 and grid1[0][2] = 1, so we still have a valid island.

Moving right again to (0,3) now we have a water / 0 cell. So we backtrack to try going down instead.

We eventually find that we can go to (2,1), and we can continue moving right until we reach (1,4). We can no longer find any valid land cell and stay in bound. So we return True and the count of subislands increment by 1.

We keep going like this to find another subisland at (3,0) and (4,1).

So the total count of subislands is 3.

Following this strategy, we can define our dfs function.

dfs(grid1,grid2,i,j,m,n):
  if i < 0 or j < 0 or i >= m or j >= n or grid2[i][j] == 0: #Check if out of bounds or not land
    return True 
  
  grid2[i][j] = 0 # We mark every cell we visited with 0
  isSubIsland = True
  if grid1[i][j] == 0: # If the corresponding cell in grid1 is not land, then we must not have a valid subisland.
    isSubIsland = False
  
  #Propagate the isSubIsland delimiter as we traverse the grid
  isSubIsland = dfs(grid1,grid2,i,j+1,m,n) and isSubIsland # move right and check if we have valid subisland
  isSubIsland = dfs(grid1,grid2,i,j-1,m,n) and isSubIsland # move left
  isSubIsland = dfs(grid1,grid2,i+1,j,m,n) and isSubIsland # move down
  isSubIsland = dfs(grid1,grid2,i-1,j,m,n) and isSubIsland # move up
  
  return isSubIsland

All there is left to do is to count up all the valid subislands.

def countSubIslands(grid1,grid2):
  count = 0
  rows = len(grid1)
  cols = len(grid1[0])
  
  for i in range(rows):
    for j in range(cols):
      if grid2[i][j] == 1:
        if dfs(grid1,grid2,i,j,rows,cols):
          count += 1
  
  return count

The time complexity is O(m * n) where m * n is the dimension of the grid. This is because we need to traverse every cell exactly once.

The space complexity is O(1) since we only need to store the count variable in extra memory.

The full solution can be found near the top of the page.

Back