The Number of Distinct Islands II problem asks you to count the number of distinct islands in a 2D grid, where an island is a group of adjacent 1s (land). Two islands are considered the same if one can be transformed into the other by rotation (90, 180, 270 degrees) and/or reflection (mirror flip). That is, islands are identical if they are the same shape under any combination of these transformations.
0s (water) and 1s (land).At first glance, it seems similar to the classic "Number of Distinct Islands" problem, where you use DFS or BFS to traverse each island and store its shape. However, the twist here is that two islands are considered the same if they are the same under any rotation or reflection.
A brute-force approach would be to store all possible transformations of each island and compare them all, but this quickly becomes inefficient. Instead, we need a way to normalize each island's shape so that all its transformations map to a unique "canonical" form. This way, we can compare islands by their canonical forms and count the distinct ones.
The key insight is: For each island, generate all 8 possible transformations (4 rotations × 2 reflections), normalize them, and use the minimal one as the canonical shape.
This approach ensures that all islands that are the same under rotation/reflection are counted as one.
Consider the following grid:
1 1 0 0 0
1 0 0 0 1
0 0 0 1 1
0 0 0 0 0
O(N^2 * K * 8), where N is the number of islands and K is the average number of cells per island.O(m * n) for grid traversal.O(K) per transformation, for 8 transformations: O(K) overall since K is small — islands are rarely huge.O(N * K) space.O(m * n * K) (since each cell belongs to at most one island).Thus, the solution is efficient for reasonable grid sizes.
To solve the Number of Distinct Islands II problem, we traverse the grid to find all islands, generate all possible rotations and reflections for each, normalize their coordinates, and select a canonical shape to represent each island. By storing these canonical forms in a set, we efficiently count the number of unique island shapes, regardless of their orientation. The key insight is normalizing and comparing all transformations, which elegantly handles the challenge of rotational and reflectional equivalence.
class Solution:
def numDistinctIslands2(self, grid):
def dfs(x, y, cells):
grid[x][y] = 0
cells.append((x, y))
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
nx, ny = x+dx, y+dy
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny]:
dfs(nx, ny, cells)
def normalize(shape):
shapes = []
for trans in transformations:
transformed = [trans(x, y) for x, y in shape]
minx = min(x for x, y in transformed)
miny = min(y for x, y in transformed)
norm = sorted((x - minx, y - miny) for x, y in transformed)
shapes.append(tuple(norm))
return min(shapes)
transformations = [
lambda x, y: (x, y),
lambda x, y: (x, -y),
lambda x, y: (-x, y),
lambda x, y: (-x, -y),
lambda x, y: (y, x),
lambda x, y: (y, -x),
lambda x, y: (-y, x),
lambda x, y: (-y, -x),
]
seen = set()
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j]:
cells = []
dfs(i, j, cells)
# Normalize to (0,0) as origin
base_x, base_y = cells[0]
shape = [(x - base_x, y - base_y) for x, y in cells]
canon = normalize(shape)
seen.add(canon)
return len(seen)
class Solution {
public:
int numDistinctIslands2(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
set<vector<pair<int,int>>> shapes;
vector<pair<int,int>> dirs = {{0,1},{1,0},{0,-1},{-1,0}};
function dfs =
[&](int x, int y, vector<pair<int,int>>& cells, int ox, int oy) {
grid[x][y] = 0;
cells.push_back({x - ox, y - oy});
for (auto& d : dirs) {
int nx = x + d.first, ny = y + d.second;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny])
dfs(nx, ny, cells, ox, oy);
}
};
auto normalize = [](vector<pair<int,int>>& shape) {
vector<vector<pair<int,int>>> forms(8);
for (auto& p : shape) {
int x = p.first, y = p.second;
forms[0].push_back({ x, y});
forms[1].push_back({ x, -y});
forms[2].push_back({-x, y});
forms[3].push_back({-x, -y});
forms[4].push_back({ y, x});
forms[5].push_back({ y, -x});
forms[6].push_back({-y, x});
forms[7].push_back({-y, -x});
}
for (auto& form : forms) {
sort(form.begin(), form.end());
int minx = form[0].first, miny = form[0].second;
for (auto& q : form) {
minx = min(minx, q.first);
miny = min(miny, q.second);
}
for (auto& q : form) {
q.first -= minx;
q.second -= miny;
}
}
sort(forms.begin(), forms.end());
return forms[0];
};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j]) {
vector<pair<int,int>> cells;
dfs(i, j, cells, i, j);
shapes.insert(normalize(cells));
}
}
}
return shapes.size();
}
};
class Solution {
public int numDistinctIslands2(int[][] grid) {
int m = grid.length, n = grid[0].length;
Set<String> shapes = new HashSet<>();
int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
List<int[]> cells = new ArrayList<>();
dfs(grid, i, j, i, j, cells, dirs);
shapes.add(normalize(cells));
}
}
}
return shapes.size();
}
private void dfs(int[][] grid, int x, int y, int ox, int oy, List<int[]> cells, int[][] dirs) {
grid[x][y] = 0;
cells.add(new int[]{x - ox, y - oy});
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] == 1) {
dfs(grid, nx, ny, ox, oy, cells, dirs);
}
}
}
private String normalize(List<int[]> shape) {
List<List<int[]>> forms = new ArrayList<>();
int[][] trans = {
{1,1},{1,-1},{-1,1},{-1,-1},
{0,1},{0,-1},{1,0},{-1,0}
};
for (int k = 0; k < 8; ++k) {
List<int[]> form = new ArrayList<>();
for (int[] p : shape) {
int x = p[0], y = p[1];
int nx, ny;
switch (k) {
case 0: nx = x; ny = y; break;
case 1: nx = x; ny = -y; break;
case 2: nx = -x; ny = y; break;
case 3: nx = -x; ny = -y; break;
case 4: nx = y; ny = x; break;
case 5: nx = y; ny = -x; break;
case 6: nx = -y; ny = x; break;
default: nx = -y; ny = -x; break;
}
form.add(new int[]{nx, ny});
}
forms.add(form);
}
String res = null;
for (List<int[]> form : forms) {
Collections.sort(form, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
int minx = form.get(0)[0], miny = form.get(0)[1];
for (int[] q : form) {
minx = Math.min(minx, q[0]);
miny = Math.min(miny, q[1]);
}
StringBuilder sb = new StringBuilder();
for (int[] q : form) {
sb.append((q[0] - minx) + ":" + (q[1] - miny) + ";");
}
String s = sb.toString();
if (res == null || s.compareTo(res) < 0) res = s;
}
return res;
}
}
var numDistinctIslands2 = function(grid) {
const m = grid.length, n = grid[0].length;
const seen = new Set();
const dirs = [[0,1],[1,0],[0,-1],[-1,0]];
function dfs(x, y, cells, ox, oy) {
grid[x][y] = 0;
cells.push([x - ox, y - oy]);
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 1) {
dfs(nx, ny, cells, ox, oy);
}
}
}
function normalize(shape) {
const forms = [];
const trans = [
([x, y]) => [ x, y],
([x, y]) => [ x, -y],
([x, y]) => [-x, y],
([x, y]) => [-x, -y],
([x, y]) => [ y, x],
([x, y]) => [ y, -x],
([x, y]) => [-y, x],
([x, y]) => [-y, -x],
];
for (const f of trans) {
const form = shape.map(f);
let minx = Math.min(...form.map(([x, _]) => x));
let miny = Math.min(...form.map(([_, y]) => y));
const norm = form.map(([x, y]) => [x - minx, y - miny])
.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
forms.push(JSON.stringify(norm));
}
forms.sort();
return forms[0];
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 1) {
const cells = [];
dfs(i, j, cells, i, j);
seen.add(normalize(cells));
}
}
}
return seen.size;
};