Number of Distinct Islands

Slug: number-of-distinct-islands

Difficulty: Medium

Id: 711086

Topic Tags: DFS, Graph, BFS, Data Structures, Algorithms

Company Tags: None

Summary

Given a matrix representing land and water with distinct island shapes, find the total number of unique islands. An island is considered distinct if it does not contain any identical shape to another.

The problem involves graph traversal (DFS/BFS) and data structure manipulation, making it an excellent example for demonstrating algorithmic thinking.

Detailed Explanation

To solve this problem, we'll use a depth-first search (DFS) approach. We iterate through each cell in the matrix, considering the current cell as the starting point of a new island. If the cell is land (1), we perform a DFS to mark all connected land cells as part of the same island.

Here's a step-by-step breakdown:

1. Initialize an empty set islands to store unique island shapes.
2. Iterate through each cell in the matrix:
   • If the cell is water (0) or has been visited before, skip it.
   • If the cell is land (1), perform a DFS to mark all connected land cells as part of the same island:
     • Mark the current cell as visited.
     • Recursively visit all neighboring cells (up, down, left, right) if they are land and unvisited.
3. After visiting each cell, check if the island shape is unique by comparing it to any previously encountered shapes in the islands set:
   • If the shape is new, add it to the islands set.
4. Return the size of the islands set, which represents the total number of distinct islands.

Time Complexity: O(M * N), where M is the number of rows and N is the number of columns in the matrix.

Space Complexity: O(M * N) for storing the visited cells during DFS.

Optimized Solutions

Java

java
public int numDistinctIslands(int[][] grid) {
    Set<String> islands = new HashSet<>();
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1) {
                String islandShape = getIslandShape(grid, i, j);
                islands.add(islandShape);
            }
        }
    }
    return islands.size();
}

private String getIslandShape(int[][] grid, int i, int j) {
    StringBuilder shape = new StringBuilder();
    while (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1) {
        shape.append(i + "," + j + " ");
        dfs(grid, i, j);
        i -= 1;
        j -= 1;
    }
    return shape.toString();
}

private void dfs(int[][] grid, int i, int j) {
    if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1) {
        grid[i][j] = 0;
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}

Python