Leetcode 2035 Solution

This article provides solution to leetcode question 2035 (count-sub-islands)

https://leetcode.com/problems/count-sub-islands

Solution

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m = len(grid1)
        n = len(grid1[0])

        def dfs(i, j):
            valid = grid1[i][j] == 1
            grid2[i][j] = 2

            directions = [
                (0, 1),
                (1, 0),
                (0, -1),
                (-1, 0),
            ]
            for di, dj in directions:
                neigh_i = i + di
                neigh_j = j + dj

                if not (0 <= neigh_i < m and 0 <= neigh_j < n):
                    continue

                if grid2[neigh_i][neigh_j] != 1:
                    continue

                valid &= dfs(neigh_i, neigh_j)
            return valid

        ans = 0
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1 and dfs(i, j):
                    ans += 1
        return ans