LeetCode Solutions Blog

Number of Distinct Islands II

Number: 711

Difficulty: Hard

Paid? Yes

Problem Description

Given an m x n binary matrix, an island is defined as a group of connected lands (cells with value 1) connected 4-directionally. Two islands are considered the same if one island can be rotated (90, 180, or 270 degrees) or reflected (horizontally or vertically) to match the other. The objective is to return the number of distinct islands under these transformation rules.

Key Insights

Use DFS or BFS to traverse and record the coordinates of cells in each island.
For each island, generate all 8 possible transformations (4 rotations and each can be reflected) and normalize them.
Convert the normalized coordinates into a canonical representation (for example, a sorted tuple) so that islands with the same shape (up to rotation/reflection) match.
Store these canonical representations in a set to count distinct islands.

Space and Time Complexity

Time Complexity: O(m * n) where m and n are the grid dimensions. Each island is processed and 8 transformations (a constant factor) are generated. Space Complexity: O(m * n) for recursion stack and storage of island coordinates and canonical shapes.

Solution

We iterate over each cell in the grid. When a cell with a 1 is found, we perform a DFS to capture all the coordinates of the island, marking cells as visited. For each island found, we generate 8 transformations corresponding to all combinations of rotations and reflections. Each transformed set of coordinates is normalized by translating them so that the smallest coordinate becomes (0, 0). We then sort and choose the lexicographically smallest transformation as the canonical representation. A set is used to track distinct canonical forms, and finally the size of this set is returned.

Code Solutions

class Solution:
    def numDistinctIslands2(self, grid: List[List[int]]) -> int:
        # Get grid dimensions
        rows, cols = len(grid), len(grid[0])
        distinct_islands = set()  # To store unique canonical shapes
        
        def dfs(x, y, cells):
            # Mark the current cell as visited and add its coordinate to the island's list
            grid[x][y] = 0
            cells.append((x, y))
            # Explore four directions
            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                    dfs(nx, ny, cells)
        
        def canonical(cells):
            shapes = []
            # There are 8 possible transformations (rotations + reflections)
            for k in range(8):
                transformed = []
                for x, y in cells:
                    if k == 0:
                        transformed.append(( x, y))
                    elif k == 1:
                        transformed.append(( x, -y))
                    elif k == 2:
                        transformed.append((-x, y))
                    elif k == 3:
                        transformed.append((-x, -y))
                    elif k == 4:
                        transformed.append(( y, x))
                    elif k == 5:
                        transformed.append(( y, -x))
                    elif k == 6:
                        transformed.append((-y, x))
                    elif k == 7:
                        transformed.append((-y, -x))
                # Sort the transformed coordinates
                transformed.sort()
                # Normalize shape: shift all coordinates so that the smallest becomes (0,0)
                origin_x, origin_y = transformed[0]
                normalized = [(x - origin_x, y - origin_y) for x, y in transformed]
                shapes.append(tuple(normalized))
            # Return the lexicographically smallest normalized shape as the canonical form
            return min(shapes)
        
        # Traverse every cell, perform DFS on islands and compute canonical shape
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    cells = []
                    dfs(i, j, cells)
                    can_shape = canonical(cells)
                    distinct_islands.add(can_shape)
                    
        return len(distinct_islands)