Leetcode 0694. Number of Distinct Islands

Problem statement

https://leetcode.com/problems/number-of-distinct-islands/

Solution

We traverse our grid either with dfs or bfs, write coordinates for each island and then normalize each island: subtract coordinate of smallest coordinate from all cells. Finally, create string from each island and put them into set and return length of this set.

Complexity

Timt and space complexity is O(mn).

Code

class Solution:
    def numDistinctIslands(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)