Problem statement

https://binarysearch.com/problems/Distinct-Islands/

Solution

Equal to Leetcode 0694. Number of Distinct Islands.

Complexity

Time and space is O(mn).

Code

class Solution:
    def solve(self, grid):
        m, n = len(grid), len(grid[0])
        neib_list = [[1,0],[-1,0],[0,-1],[0,1]]
        islands = defaultdict(list)
        isl_set, count = set(), 0
        
        def dfs(t, i, j):
            if i<0 or j<0 or i>=m or j>=n or grid[i][j] != 1: return
            islands[t].append((i, j))
            grid[i][j] = '#'
            for x, y in neib_list: dfs(t, x+i, y+j)
        
        for i,j in product(range(m), range(n)):
            if grid[i][j] == 1:
                dfs(count, i, j)
                count += 1
                    
        for i in range(count):
            x, y = min(islands[i])
            isl_set.add("+".join([str([i-x,j-y]) for i,j in islands[i]]))
        
        return len(isl_set)