Number of Distinct Islands
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 <= 50wherem = grid.length,n = grid[0].lengthgrid[i][j]is0(water) or1(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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(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.O(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.
- For each unvisited land cell, flood fill to gather the island's cells (marking them as water).
- Subtract the island's minimum row and minimum column from every cell; sort the cells.
- Linear search the list of distinct shapes for an equal list; append if none.
- 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;
}
}class Solution:
def numDistinctIslands(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
shapes = []
def collect(r: int, c: int, cells: List[Tuple[int, int]]) -> None:
if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] != 1:
return
grid[r][c] = 0
cells.append((r, c))
collect(r + 1, c, cells)
collect(r - 1, c, cells)
collect(r, c + 1, cells)
collect(r, c - 1, cells)
for i in range(m):
for j in range(n):
if grid[i][j] != 1:
continue
cells = []
collect(i, j, cells)
min_r = min(r for r, _ in cells)
min_c = min(c for _, c in cells)
shape = sorted((r - min_r, c - min_c) for r, c in cells)
found = False
for s in shapes:
if s == shape:
found = True
break
if not found:
shapes.append(shape)
return len(shapes)class Solution {
public:
int numDistinctIslands(vector<vector<int>>& grid) {
vector<vector<pair<int, int>>> shapes;
for (int i = 0; i < (int)grid.size(); i++)
for (int j = 0; j < (int)grid[0].size(); j++) {
if (grid[i][j] != 1) continue;
vector<pair<int, int>> cells;
collect(grid, i, j, cells);
int minR = INT_MAX, minC = INT_MAX;
for (auto& c : cells) { minR = min(minR, c.first); minC = min(minC, c.second); }
for (auto& c : cells) { c.first -= minR; c.second -= minC; }
sort(cells.begin(), cells.end());
bool found = false;
for (auto& s : shapes)
if (s == cells) { found = true; break; }
if (!found) shapes.push_back(cells);
}
return shapes.size();
}
private:
void collect(vector<vector<int>>& g, int r, int c, vector<pair<int, int>>& cells) {
if (r < 0 || c < 0 || r >= (int)g.size() || c >= (int)g[0].size() || g[r][c] != 1) return;
g[r][c] = 0;
cells.push_back({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);
}
};function numDistinctIslands(grid) {
const m = grid.length, n = grid[0].length;
const shapes = [];
const collect = (r, c, cells) => {
if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] !== 1) return;
grid[r][c] = 0;
cells.push([r, c]);
collect(r + 1, c, cells);
collect(r - 1, c, cells);
collect(r, c + 1, cells);
collect(r, c - 1, cells);
};
const same = (a, b) => {
if (a.length !== b.length) return false;
for (let i = 0; i < a.length; i++)
if (a[i][0] !== b[i][0] || a[i][1] !== b[i][1]) return false;
return true;
};
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++) {
if (grid[i][j] !== 1) continue;
const cells = [];
collect(i, j, cells);
let minR = Infinity, minC = Infinity;
for (const c of cells) { minR = Math.min(minR, c[0]); minC = Math.min(minC, c[1]); }
for (const c of cells) { c[0] -= minR; c[1] -= minC; }
cells.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
let found = false;
for (const s of shapes)
if (same(s, cells)) { found = true; break; }
if (!found) shapes.push(cells);
}
return shapes.length;
}2Optimal (DFS offset signature in a hash set)
O(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.O(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.
- For each land cell (r0, c0) in row-major order: run DFS that sinks the island.
- On visiting (r, c), append
(r - r0),(c - c0);to a string builder. - Add the finished string to a hash set.
- 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);
}
}class Solution:
def numDistinctIslands(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
shapes = set()
def dfs(r: int, c: int, r0: int, c0: int, sig: List[str]) -> None:
if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] != 1:
return
grid[r][c] = 0
sig.append(f"{r - r0},{c - c0};")
dfs(r + 1, c, r0, c0, sig)
dfs(r - 1, c, r0, c0, sig)
dfs(r, c + 1, r0, c0, sig)
dfs(r, c - 1, r0, c0, sig)
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
sig = []
dfs(i, j, i, j, sig)
shapes.add("".join(sig))
return len(shapes)class Solution {
public:
int numDistinctIslands(vector<vector<int>>& grid) {
unordered_set<string> shapes;
for (int i = 0; i < (int)grid.size(); i++)
for (int j = 0; j < (int)grid[0].size(); j++)
if (grid[i][j] == 1) {
string sig;
dfs(grid, i, j, i, j, sig);
shapes.insert(sig);
}
return shapes.size();
}
private:
void dfs(vector<vector<int>>& g, int r, int c, int r0, int c0, string& sig) {
if (r < 0 || c < 0 || r >= (int)g.size() || c >= (int)g[0].size() || g[r][c] != 1) return;
g[r][c] = 0;
sig += to_string(r - r0) + "," + to_string(c - c0) + ";";
dfs(g, r + 1, c, r0, c0, sig);
dfs(g, r - 1, c, r0, c0, sig);
dfs(g, r, c + 1, r0, c0, sig);
dfs(g, r, c - 1, r0, c0, sig);
}
};function numDistinctIslands(grid) {
const m = grid.length, n = grid[0].length;
const shapes = new Set();
const dfs = (r, c, r0, c0, sig) => {
if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] !== 1) return;
grid[r][c] = 0;
sig.push((r - r0) + ',' + (c - c0) + ';');
dfs(r + 1, c, r0, c0, sig);
dfs(r - 1, c, r0, c0, sig);
dfs(r, c + 1, r0, c0, sig);
dfs(r, c - 1, r0, c0, sig);
};
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (grid[i][j] === 1) {
const sig = [];
dfs(i, j, i, j, sig);
shapes.add(sig.join(''));
}
return shapes.size;
}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.