Number of Distinct Islands

Problem#

Given a binary grid, an island is a 4-connected group of 1s. Two islands have the same shape if one can be translated (no rotation/reflection) to the other. Return the count of distinct island shapes.

Examples#

[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]] → 1.
[[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]] → 3.

Constraints#

1 <= m, n <= 50.

Hints#

Hint 1

Encode each DFS as a string: at each step append a direction marker, including a “back” marker on returns.

Hint 2

Storing direction tokens including backtrack steps is crucial — otherwise shapes “T” and ”+” collide.

Approach#

DFS each island. Record the path as a string with characters for each move direction (U, D, L, R) and a back-marker (B) when returning. Insert finished signatures into a set; answer is the set size.

Solution#

class Solution {
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        unordered_set<string> shapes;
        string path;
        function<void(int,int,char)> dfs = [&](int r, int c, char came) {
            if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1) return;
            grid[r][c] = 0;
            path.push_back(came);
            dfs(r - 1, c, 'U');
            dfs(r + 1, c, 'D');
            dfs(r, c - 1, 'L');
            dfs(r, c + 1, 'R');
            path.push_back('B');
        };
        for (int r = 0; r < m; ++r)
            for (int c = 0; c < n; ++c)
                if (grid[r][c] == 1) {
                    path.clear();
                    dfs(r, c, 'S');
                    shapes.insert(path);
                }
        return shapes.size();
    }
};

func numDistinctIslands(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    shapes := map[string]bool{}
    var path []byte
    var dfs func(r, c int, came byte)
    dfs = func(r, c int, came byte) {
        if r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1 {
            return
        }
        grid[r][c] = 0
        path = append(path, came)
        dfs(r-1, c, 'U')
        dfs(r+1, c, 'D')
        dfs(r, c-1, 'L')
        dfs(r, c+1, 'R')
        path = append(path, 'B')
    }
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if grid[r][c] == 1 {
                path = path[:0]
                dfs(r, c, 'S')
                shapes[string(path)] = true
            }
        }
    }
    return len(shapes)
}

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        shapes = set()
        path: List[str] = []

        def dfs(r: int, c: int, came: str) -> None:
            if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != 1:
                return
            grid[r][c] = 0
            path.append(came)
            dfs(r - 1, c, 'U')
            dfs(r + 1, c, 'D')
            dfs(r, c - 1, 'L')
            dfs(r, c + 1, 'R')
            path.append('B')

        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    path.clear()
                    dfs(r, c, 'S')
                    shapes.add(''.join(path))
        return len(shapes)

function numDistinctIslands(grid) {
    const m = grid.length, n = grid[0].length;
    const shapes = new Set();
    let path = [];
    const dfs = (r, c, came) => {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== 1) return;
        grid[r][c] = 0;
        path.push(came);
        dfs(r - 1, c, 'U');
        dfs(r + 1, c, 'D');
        dfs(r, c - 1, 'L');
        dfs(r, c + 1, 'R');
        path.push('B');
    };
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1) {
                path = [];
                dfs(r, c, 'S');
                shapes.add(path.join(''));
            }
        }
    }
    return shapes.size;
}

class Solution {
    private int m, n;
    private int[][] grid;
    private StringBuilder path;

    public int numDistinctIslands(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        Set<String> shapes = new HashSet<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    path = new StringBuilder();
                    dfs(r, c, 'S');
                    shapes.add(path.toString());
                }
            }
        }
        return shapes.size();
    }

    private void dfs(int r, int c, char came) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1) return;
        grid[r][c] = 0;
        path.append(came);
        dfs(r - 1, c, 'U');
        dfs(r + 1, c, 'D');
        dfs(r, c - 1, 'L');
        dfs(r, c + 1, 'R');
        path.append('B');
    }
}

function numDistinctIslands(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const shapes = new Set<string>();
    let path: string[] = [];
    const dfs = (r: number, c: number, came: string): void => {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== 1) return;
        grid[r][c] = 0;
        path.push(came);
        dfs(r - 1, c, 'U');
        dfs(r + 1, c, 'D');
        dfs(r, c - 1, 'L');
        dfs(r, c + 1, 'R');
        path.push('B');
    };
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1) {
                path = [];
                dfs(r, c, 'S');
                shapes.add(path.join(''));
            }
        }
    }
    return shapes.size;
}

Editorial#

The 'B' (backtrack) marker is what makes the signature canonical: without it, an island shaped like [[1,1],[1,0]] (an “L”) looks identical to [[1,1],[0,1]] because both touch three cells. Recording the backtrack ensures branching points differ in their signatures.

Complexity#

Time: O(M * N).
Space: O(M * N) for set.

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#