Problem Description

The "Number of Distinct Islands" problem asks you to determine how many unique island shapes exist in a given 2D grid. The grid is composed of 0s (representing water) and 1s (representing land). An island is a group of horizontally or vertically connected 1s. Two islands are considered the same if and only if one can be translated (slid up/down/left/right) to equal the other. Rotations and reflections do not count; only translation is allowed. The task is to count the number of distinct island shapes present in the grid.

• Each island must be made up of adjacent 1s (no diagonals).
• Islands are considered the same if they have the same shape and structure after translation.
• Do not count duplicate island shapes.
• Input is a 2D list or array grid of size m x n containing only 0s and 1s.

Thought Process

At first glance, one might think to simply count islands using a standard DFS or BFS. However, the key challenge is distinguishing between island shapes. We need a way to represent and compare the structure of each island, so that two islands with the same shape (regardless of their position) are considered identical.

A brute-force approach might attempt to store the coordinates of every island and compare them directly, but this would be inefficient and tricky due to translation. Instead, we need a method to normalize each island's shape so it can be compared easily. This leads us to the idea of recording the relative positions of all land cells in an island with respect to a fixed starting point, such as the first cell visited during DFS. By doing so, we can encode each island's structure in a way that's independent of its location in the grid.

Solution Approach

The optimized solution uses Depth-First Search (DFS) to explore each island, recording the relative positions of each land cell. We then store each island's relative structure in a set to automatically filter out duplicates. Here's how we do it:

1. Iterate through the grid: For each cell, if it's a 1 (land) and hasn't been visited, start a DFS.
2. DFS Traversal: During DFS, for every land cell we visit, record its position relative to the starting cell of this island (e.g., (row - baseRow, col - baseCol)).
3. Shape Representation: Store the sequence of these relative positions (in a tuple or string) to represent the island's shape.
4. Distinct Shapes: Use a set to keep all unique shapes found. Since sets only allow unique entries, duplicate shapes are automatically ignored.
5. Result: The number of distinct islands is simply the size of this set.

This approach is efficient and elegant, as it leverages DFS for island discovery and set operations for uniqueness.

Example Walkthrough

Consider the following grid:

    1 1 0 0 0
    1 0 0 0 1
    0 0 0 1 1
  

1. Start at (0,0): it's land. Begin DFS, marking visited cells and recording relative positions:
   • (0,0): base cell → (0,0)
   • (0,1): right → (0,1)
   • (1,0): down → (1,0)
   Shape: [(0,0), (0,1), (1,0)]
2. Next unvisited land is at (1,4): New DFS:
   • (1,4): base cell → (0,0)
   • (2,3): down-left → (1,-1)
   • (2,4): down → (1,0)
   Shape: [(0,0), (1,-1), (1,0)]
3. Store both shapes in a set. Since their relative positions differ, both are distinct. The answer is 2.

Time and Space Complexity

• Brute-force: If you tried to compare every island's absolute coordinates, it could be O((mn)^2) for m rows and n columns due to repeated comparisons.
• Optimized (DFS + shape encoding):
  • Time Complexity: O(mn), since each cell is visited at most once during DFS.
  • Space Complexity: O(mn), for the visited matrix and the set of shapes (in the worst case, every cell is land and each island is unique).

Summary

The key insight is to record each island's shape using relative coordinates, making the solution robust to translation. By using DFS to explore islands and a set to collect unique shapes, we achieve an efficient and elegant solution. This method ensures that islands with the same structure are counted only once, regardless of their position in the grid.

Code Implementation

class Solution:
    def numDistinctIslands(self, grid):
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        visited = [[False]*n for _ in range(m)]
        shapes = set()

        def dfs(r, c, base_r, base_c, shape):
            if (0 <= r < m and 0 <= c < n and 
                grid[r][c] == 1 and not visited[r][c]):
                visited[r][c] = True
                shape.append((r - base_r, c - base_c))
                dfs(r+1, c, base_r, base_c, shape)
                dfs(r-1, c, base_r, base_c, shape)
                dfs(r, c+1, base_r, base_c, shape)
                dfs(r, c-1, base_r, base_c, shape)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and not visited[i][j]:
                    shape = []
                    dfs(i, j, i, j, shape)
                    shapes.add(tuple(shape))
        return len(shapes)
      

class Solution {
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        set<vector<pair<int,int>>> shapes;

        function<void(int,int,int,int,vector<pair<int,int>>&)> dfs = 
            [&](int r, int c, int base_r, int base_c, vector<pair<int,int>>& shape) {
            if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0 || visited[r][c])
                return;
            visited[r][c] = true;
            shape.push_back({r - base_r, c - base_c});
            dfs(r+1, c, base_r, base_c, shape);
            dfs(r-1, c, base_r, base_c, shape);
            dfs(r, c+1, base_r, base_c, shape);
            dfs(r, c-1, base_r, base_c, shape);
        };

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    vector<pair<int,int>> shape;
                    dfs(i, j, i, j, shape);
                    shapes.insert(shape);
                }
            }
        }
        return shapes.size();
    }
};
      

class Solution {
    public int numDistinctIslands(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        Set<String> shapes = new HashSet<>();

        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    List<String> shape = new ArrayList<>();
                    dfs(grid, visited, i, j, i, j, shape);
                    shapes.add(String.join(";", shape));
                }
            }
        }
        return shapes.size();
    }

    private void dfs(int[][] grid, boolean[][] visited, int r, int c, int baseR, int baseC, List<String> shape) {
        int m = grid.length, n = grid[0].length;
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0 || visited[r][c])
            return;
        visited[r][c] = true;
        shape.add((r - baseR) + "," + (c - baseC));
        dfs(grid, visited, r+1, c, baseR, baseC, shape);
        dfs(grid, visited, r-1, c, baseR, baseC, shape);
        dfs(grid, visited, r, c+1, baseR, baseC, shape);
        dfs(grid, visited, r, c-1, baseR, baseC, shape);
    }
}
      

var numDistinctIslands = function(grid) {
    const m = grid.length, n = grid[0].length;
    const visited = Array.from({length: m}, () => Array(n).fill(false));
    const shapes = new Set();

    function dfs(r, c, baseR, baseC, shape) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === 0 || visited[r][c])
            return;
        visited[r][c] = true;
        shape.push([r - baseR, c - baseC]);
        dfs(r+1, c, baseR, baseC, shape);
        dfs(r-1, c, baseR, baseC, shape);
        dfs(r, c+1, baseR, baseC, shape);
        dfs(r, c-1, baseR, baseC, shape);
    }

    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] === 1 && !visited[i][j]) {
                const shape = [];
                dfs(i, j, i, j, shape);
                shapes.add(JSON.stringify(shape));
            }
        }
    }
    return shapes.size;
};