Problem statement

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

Solution

This is natural extension of problem 0694 Number of Distinct Islands, but here we can rotate and reflect our islands. Let us use dfs or bfs to get dictionary of islands. Next, for each island, we need to generate all rotations and reflections — all in total, including original, normalize them: subtract min value from all nodes and sort. Note, that we did not sort for problem 0694, because there we always traverse two equal islands starting with the same cell, because we traverse our grid line by line. Here we need to sort values in each island.

Complexity

Time complexity is O(mn * log(mn)), because we can potentially have one big island. Space complexity is O(mn).

Code

class Solution:
    def numDistinctIslands2(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 not 0 <= i < m or not 0 <= 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)
            
        def rot(island, i,j):
            new = sorted([(x*i, y*j) for x, y in island])
            u, v = min(new)
            return [(x-u, y-v) for x, y in new]
            
        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):
            found = 0
            q1 = islands[i]
            q2 = [(b, a) for a, b in q1]
            for i1,i2 in product(range(-1, 2, 2), range(-1, 2, 2)):
                att1 = "+".join([str(s) for s in rot(q1, i1, i2)])
                att2 = "+".join([str(s) for s in rot(q2, i1, i2)])
                if att1 in isl_set or att2 in isl_set: found = 1
            
            if found == 0: isl_set.add(att1)
            
        return len(isl_set)

Remark

Good question: is time complexity can be reduced to O(mn) and my intuition tell that it is possible: we can use dfs as we did, but now directly write number of island in our grid. Then we traverse our grid line by line and form our islands: they will be already sorted (but not normalized) Then we can rotate/reflect our grid and repeat our procedure (or traverse it in other order and form coordinates on flight. Time complexity finally will be O(8mn), but because of small constraints of problem, it will not work faster, may be even slower.