Number of Distinct Islands

Medium Graphs Matrix Graphs Original on LeetCode

Number of Distinct Islands is a medium graphs problem solved with the matrix graphs pattern. The best approach, optimal (dfs offset signature in a hash set), runs in O(m · n) time and O(m · n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (compare normalised shapes pairwise) up.

Problem

You are given an m × n binary grid where 1 is land and 0 is water. An island is a group of land cells connected horizontally or vertically.

Two islands have the same shape if one can be moved onto the other by shifting it (up, down, left, right) only. Rotating or mirroring is not allowed, so a shape and its mirror image are different.

Return the number of distinct island shapes in the grid.

Examples

Example 1

Input
grid = [[1,1,0,1,1],[1,0,0,1,0],[0,0,0,0,0],[0,1,1,0,1],[0,1,0,0,1]]
Output
2
Why
Three islands are the same 3-cell corner shape (just shifted); the fourth is a vertical pair of cells.

Example 2

Input
grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1]]
Output
2
Why
Both islands have 3 cells, but one is the other rotated by 180°. Rotations do not count as the same shape.

Example 3

Input
grid = [[1,0,1],[0,1,0],[1,0,1]]
Output
1
Why
Five single-cell islands (diagonal neighbours are not connected), all the same shape.

Constraints

  • 1 <= m, n <= 50 where m = grid.length, n = grid[0].length
  • grid[i][j] is 0 (water) or 1 (land); land connects only up, down, left and right.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (compare normalised shapes pairwise)O(m · n · k)O(m · n)
Optimal (DFS offset signature in a hash set)O(m · n)O(m · n)

1Brute force (compare normalised shapes pairwise)

TimeO(m · n · k)Each new island is compared with up to k earlier shapes, and each comparison can touch up to all of its cells; sorting adds a log factor per island.
SpaceO(m · n)The stored shapes together hold at most m · n cells.

Collect each island's cells, shift them so the minimum row and column become 0, and sort them. Compare the new shape against every distinct shape found so far; keep it only if no match exists.

  1. For each unvisited land cell, flood fill to gather the island's cells (marking them as water).
  2. Subtract the island's minimum row and minimum column from every cell; sort the cells.
  3. Linear search the list of distinct shapes for an equal list; append if none.
  4. Return the number of distinct shapes.
class Solution {
    public int numDistinctIslands(int[][] grid) {
        List<List<int[]>> shapes = new ArrayList<>();
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] != 1) continue;
                List<int[]> cells = new ArrayList<>();
                collect(grid, i, j, cells);
                int minR = Integer.MAX_VALUE, minC = Integer.MAX_VALUE;
                for (int[] c : cells) { minR = Math.min(minR, c[0]); minC = Math.min(minC, c[1]); }
                for (int[] c : cells) { c[0] -= minR; c[1] -= minC; }
                cells.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
                boolean found = false;
                for (List<int[]> s : shapes)
                    if (same(s, cells)) { found = true; break; }
                if (!found) shapes.add(cells);
            }
        return shapes.size();
    }

    private void collect(int[][] g, int r, int c, List<int[]> cells) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != 1) return;
        g[r][c] = 0;
        cells.add(new int[] { r, c });
        collect(g, r + 1, c, cells);
        collect(g, r - 1, c, cells);
        collect(g, r, c + 1, cells);
        collect(g, r, c - 1, cells);
    }

    private boolean same(List<int[]> a, List<int[]> b) {
        if (a.size() != b.size()) return false;
        for (int i = 0; i < a.size(); i++)
            if (a.get(i)[0] != b.get(i)[0] || a.get(i)[1] != b.get(i)[1]) return false;
        return true;
    }
}

2Optimal (DFS offset signature in a hash set)

TimeO(m · n)Every cell is visited once, and the total signature length is proportional to the number of land cells; hashing them is linear too.
SpaceO(m · n)The set of signatures plus the DFS recursion stack, both bounded by the grid size.

Start each island's DFS from the first land cell met in row-major order and record every visited cell as its offset from that start, in visiting order. The DFS visits neighbours in a fixed order, so two islands that are shifts of each other produce exactly the same offset string. Put the strings in a hash set and return its size.

  1. For each land cell (r0, c0) in row-major order: run DFS that sinks the island.
  2. On visiting (r, c), append (r - r0),(c - c0); to a string builder.
  3. Add the finished string to a hash set.
  4. Return the set's size.
class Solution {
    public int numDistinctIslands(int[][] grid) {
        Set<String> shapes = new HashSet<>();
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++)
                if (grid[i][j] == 1) {
                    StringBuilder sb = new StringBuilder();
                    dfs(grid, i, j, i, j, sb);
                    shapes.add(sb.toString());
                }
        return shapes.size();
    }

    private void dfs(int[][] g, int r, int c, int r0, int c0, StringBuilder sb) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != 1) return;
        g[r][c] = 0;
        sb.append(r - r0).append(',').append(c - c0).append(';');
        dfs(g, r + 1, c, r0, c0, sb);
        dfs(g, r - 1, c, r0, c0, sb);
        dfs(g, r, c + 1, r0, c0, sb);
        dfs(g, r, c - 1, r0, c0, sb);
    }
}

Edge cases to test

  • No land at all: answer 0
  • Mirror images and rotations of a shape are different shapes
  • Two islands with the same number of cells but different layouts
  • One island covering the whole grid

Hints

Hint 1

Two islands are the same when one is a pure shift of the other. Describe each island relative to a fixed reference cell.

Hint 2

Scan in row-major order: the first land cell you meet is the island's top-most, left-most cell. Store every cell as (row - r0, col - c0).

Hint 3

If you visit cells in a fixed DFS order from that start, equal shapes produce the same sequence of offsets, so the sequence can go straight into a hash set.

FAQ

What is the best time complexity for Number of Distinct Islands?

Optimal (DFS offset signature in a hash set) runs in O(m · n) time and O(m · n) extra space. Every cell is visited once, and the total signature length is proportional to the number of land cells; hashing them is linear too.

Which pattern does Number of Distinct Islands use?

It is a graphs problem that uses the matrix graphs pattern. Other problems with the same pattern: Flood Fill, Maximum Number of Points From Grid Queries, Contain Virus.

Is there a brute force solution for Number of Distinct Islands?

Yes. Brute force (compare normalised shapes pairwise) takes O(m · n · k) time and O(m · n) space. Collect each island's cells, shift them so the minimum row and column become 0, and sort them.

Which edge cases should I test for Number of Distinct Islands?

No land at all: answer 0; Mirror images and rotations of a shape are different shapes; Two islands with the same number of cells but different layouts; One island covering the whole grid.