LeetCode Solutions Blog

Number of Distinct Islands

Number: 694

Difficulty: Medium

Paid? Yes

Problem Description

Given an m x n binary matrix grid, an island is a group of 1's (lands) connected 4-directionally (horizontally or vertically). All four edges of the grid are surrounded by water (0's). Two islands are considered the same if one island can be translated (shifted) to coincide exactly with the other – rotations and reflections are not allowed. The task is to return the number of distinct islands.

Key Insights

Use DFS/BFS to traverse and mark each island.
For each island, record its shape relative to a starting coordinate to allow translation invariance.
Represent the island's shape as a unique signature (e.g., tuple or string of relative positions).
Use a set (or hash table) to store unique shapes.

Space and Time Complexity

Time Complexity: O(m * n) as each cell is visited once. Space Complexity: O(m * n) in the worst-case due to recursion stack and storing island shapes.

Solution

Use depth-first search (DFS) to explore the grid. When an unvisited land cell (1) is encountered, initiate a DFS to traverse the entire island. Record each land cell's coordinates relative to the starting position of the island. This relative representation is invariant under translation, making it possible to compare island shapes. Store the canonical shape signature (for example, as a tuple or string) in a set to ensure uniqueness. Finally, return the size of the set as the number of distinct islands.

Code Solutions

def numDistinctIslands(grid):
    # Get the number of rows and columns
    rows, cols = len(grid), len(grid[0])
    # Set to store unique island shapes
    distinct_shapes = set()
    
    # DFS function to explore the island and record its relative shape
    def dfs(r, c, origin_r, origin_c, shape):
        # Check boundaries and if the cell is unvisited land
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == 0:
            return
        # Mark the cell as visited by setting it to 0
        grid[r][c] = 0
        # Record the relative position from the origin of this island
        shape.append((r - origin_r, c - origin_c))
        # Explore all 4-directionally adjacent cells
        dfs(r + 1, c, origin_r, origin_c, shape)
        dfs(r - 1, c, origin_r, origin_c, shape)
        dfs(r, c + 1, origin_r, origin_c, shape)
        dfs(r, c - 1, origin_r, origin_c, shape)
    
    # Iterate over every cell in the grid
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                shape = []
                dfs(i, j, i, j, shape)
                # Convert the shape list to a tuple of sorted coordinates for canonical form
                distinct_shapes.add(tuple(sorted(shape)))
    
    # The number of distinct islands is the size of the set
    return len(distinct_shapes)

# Example usage:
grid = [[1,1,0,0,0],
        [1,1,0,0,0],
        [0,0,0,1,1],
        [0,0,0,1,1]]
print(numDistinctIslands(grid))  # Output: 1