Problem statement

https://binarysearch.com/problems/Intersection-of-Two-Maps/

Solution

Similar to Leetcode 1905. Count Sub Islands, we can create all islands and then compare them.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, A, B):
        def process_grid(g):
            m, n, count = len(g), len(g[0]), 0
            neib_list = [[1,0],[-1,0],[0,-1],[0,1]]
            islands = defaultdict(set)
            isl_id = {}
            
            def dfs(t, i, j):
                if i<0 or j<0 or i>=m or j>=n or g[i][j] != 1: return
                islands[t].add((i,j))
                g[i][j] = '#'
                for x, y in neib_list: dfs(t, x+i, y+j)
            
            for i,j in product(range(m), range(n)):
                if g[i][j] == 1:
                    dfs(count, i, j)
                    count += 1  
            return set(tuple(x) for x in islands.values())

        return len(process_grid(A) & process_grid(B))