Problem statement

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

Solution

The idea is to traverse matrix B, and check how many element from this each island we have in B were visited in A. We are interseted only in such islands, that have all these elements in A.

Complexity

Time and space is O(mn).

Code

class Solution:
    def countSubIslands(self, A, B):
        m, n, res = len(A), len(A[0]), 0
        neibs = [[0, 1], [0, -1], [-1, 0], [1, 0]]
        def dfs(x, y):
            if x < 0 or y < 0 or x >= m or y >= n or B[x][y] == 0:
                return [0, 0]
            B[x][y] = 0
            res = [A[x][y], 1]
            for dx, dy in neibs:
                cnt1, cnt2 = dfs(x + dx, y + dy)
                res[0] += cnt1
                res[1] += cnt2
            return res
        
        for x in range(m):
            for y in range(n):
                cnt1, cnt2 = dfs(x, y)
                res += (cnt1 == cnt2 > 0)
        
        return res