Problem statement

Given a binary matrix grid, an island is a maximal group of 1s connected up, down, left or right.

Two islands are considered the same if one can be translated onto the other — rotations and reflections do not count. Return the number of distinct islands.

Example 1

Input: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
Output: 1

Example 2

Input: grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
Output: 3

Example 3

Input: grid = [[0]]
Output: 0

Constraints

• 1 <= grid.length, grid[i].length <= 12
• grid[i][j] is 0 or 1.

Hints for Number of Distinct Islands

1. Hint 1

   Walk each island once and record its cells relative to the first cell you entered.

2. Hint 2

   Sorting those relative coordinates gives a canonical shape independent of traversal order.

3. Hint 3

   Store the canonical shapes in a set and return its size.

How to solve Number of Distinct Islands

Record each island's cells relative to its entry cell, sort them into a canonical shape, and count distinct shapes with a set.

Approach

1. For each unvisited land cell, traverse its island collecting (r - r0, c - c0).
2. Add the sorted tuple of offsets to a set.
3. Return the set's size.

Why it works

Translation-equivalent islands have identical offset sets from their top-left-most cell, and sorting removes traversal-order differences.

Complexity

• Time — O(m · n · log)
• Space — O(m · n)

Pitfalls

• Entering an island at its row-major first cell makes the offsets canonical; sorting is belt-and-braces.

Reference solution

Python

def numDistinctIslands(grid) -> int:
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    shapes = set()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1 or seen[r][c]:
                continue
            seen[r][c] = True
            stack = [(r, c)]
            cells = []
            while stack:
                cr, cc = stack.pop()
                cells.append((cr - r, cc - c))
                for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and not seen[nr][nc]:
                        seen[nr][nc] = True
                        stack.append((nr, nc))
            shapes.add(tuple(sorted(cells)))
    return len(shapes)

Java

public static int numDistinctIslands(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    boolean[][] seen = new boolean[rows][cols];
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    Set<String> shapes = new HashSet<>();
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != 1 || seen[r][c]) continue;
            seen[r][c] = true;
            Deque<int[]> stack = new ArrayDeque<>();
            stack.push(new int[]{r, c});
            List<String> cells = new ArrayList<>();
            while (!stack.isEmpty()) {
                int[] cell = stack.pop();
                cells.add((cell[0] - r) + "," + (cell[1] - c));
                for (int d = 0; d < 4; d++) {
                    int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                    if (grid[nr][nc] != 1 || seen[nr][nc]) continue;
                    seen[nr][nc] = true;
                    stack.push(new int[]{nr, nc});
                }
            }
            Collections.sort(cells);
            shapes.add(String.join("|", cells));
        }
    }
    return shapes.size();
}

C++

int numDistinctIslands(vector<vector<int>>& grid) {
    int rows = (int) grid.size(), cols = (int) grid[0].size();
    vector<vector<bool>> seen(rows, vector<bool>(cols, false));
    int dr[4] = {1, -1, 0, 0};
    int dc[4] = {0, 0, 1, -1};
    set<string> shapes;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != 1 || seen[r][c]) continue;
            seen[r][c] = true;
            vector<pair<int,int>> stack;
            stack.push_back(make_pair(r, c));
            vector<string> cells;
            while (!stack.empty()) {
                pair<int,int> cell = stack.back();
                stack.pop_back();
                cells.push_back(to_string(cell.first - r) + "," + to_string(cell.second - c));
                for (int d = 0; d < 4; d++) {
                    int nr = cell.first + dr[d], nc = cell.second + dc[d];
                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                    if (grid[nr][nc] != 1 || seen[nr][nc]) continue;
                    seen[nr][nc] = true;
                    stack.push_back(make_pair(nr, nc));
                }
            }
            sort(cells.begin(), cells.end());
            string key;
            for (size_t i = 0; i < cells.size(); i++) {
                if (i > 0) key += "|";
                key += cells[i];
            }
            shapes.insert(key);
        }
    }
    return (int) shapes.size();
}

JavaScript

var numDistinctIslands = function(grid) {
    const rows = grid.length, cols = grid[0].length;
    const seen = [];
    for (let r = 0; r < rows; r++) {
        const row = [];
        for (let c = 0; c < cols; c++) row.push(false);
        seen.push(row);
    }
    const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    const shapes = {};
    let count = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] !== 1 || seen[r][c]) continue;
            seen[r][c] = true;
            const stack = [[r, c]];
            const cells = [];
            while (stack.length > 0) {
                const cell = stack.pop();
                cells.push((cell[0] - r) + "," + (cell[1] - c));
                for (let d = 0; d < 4; d++) {
                    const nr = cell[0] + dr[d], nc = cell[1] + dc[d];
                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                    if (grid[nr][nc] !== 1 || seen[nr][nc]) continue;
                    seen[nr][nc] = true;
                    stack.push([nr, nc]);
                }
            }
            cells.sort();
            const key = cells.join("|");
            if (shapes[key] !== true) {
                shapes[key] = true;
                count++;
            }
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium