Number of Distinct Islands II
Problem
Two islands are 'the same' if related by translation, rotation (90°), or reflection. Count distinct.
grid 4×5 with two islands related by reflection1def num_distinct_islands2(grid):
m, n = len(grid), len(grid[0]); seen = set(); shapes = set()
def dfs(r, c, pts):
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0 or (r, c) in seen: return
seen.add((r, c)); pts.append((r, c))
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): dfs(r + dr, c + dc, pts)
def canon(pts):
forms = []
for sx, sy, sw in [(1,1,0),(1,-1,0),(-1,1,0),(-1,-1,0),(1,1,1),(1,-1,1),(-1,1,1),(-1,-1,1)]:
rot = [((sx*p[1], sy*p[0]) if sw else (sx*p[0], sy*p[1])) for p in pts]
rot.sort()
forms.append(tuple((a - rot[0][0], b - rot[0][1]) for a, b in rot))
return min(forms)
for r in range(m):
for c in range(n):
if grid[r][c] == 1 and (r, c) not in seen:
pts = []; dfs(r, c, pts); shapes.add(canon(pts))
return len(shapes)function numDistinctIslands2(grid) {
const m = grid.length, n = grid[0].length;
const seen = new Set(); const shapes = new Set();
const dfs = (r, c, pts) => {
const k = r + ',' + c;
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === 0 || seen.has(k)) return;
seen.add(k); pts.push([r, c]);
for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) dfs(r + dr, c + dc, pts);
};
const canon = pts => {
const T = [[1,1,0],[1,-1,0],[-1,1,0],[-1,-1,0],[1,1,1],[1,-1,1],[-1,1,1],[-1,-1,1]];
let best = null;
for (const [sx, sy, sw] of T) {
const r = pts.map(p => sw ? [sx*p[1], sy*p[0]] : [sx*p[0], sy*p[1]]);
r.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const norm = r.map(p => [p[0] - r[0][0], p[1] - r[0][1]]);
const s = norm.map(p => p.join(',')).join('|');
if (best === null || s < best) best = s;
}
return best;
};
for (let r = 0; r < m; r++) for (let c = 0; c < n; c++)
if (grid[r][c] === 1 && !seen.has(r + ',' + c)) { const pts = []; dfs(r, c, pts); shapes.add(canon(pts)); }
return shapes.size;
}int numDistinctIslands2(int[][] grid) {
int m = grid.length, n = grid[0].length;
boolean[][] seen = new boolean[m][n];
Set<String> shapes = new HashSet<>();
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
int[][] T = {{1,1,0},{1,-1,0},{-1,1,0},{-1,-1,0},{1,1,1},{1,-1,1},{-1,1,1},{-1,-1,1}};
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (grid[r][c] == 1 && !seen[r][c]) {
List<int[]> pts = new ArrayList<>();
Deque<int[]> st = new ArrayDeque<>();
st.push(new int[]{r, c}); seen[r][c] = true;
while (!st.isEmpty()) {
int[] p = st.pop(); pts.add(p);
for (int[] d : dirs) {
int nr = p[0] + d[0], nc = p[1] + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1 && !seen[nr][nc]) {
seen[nr][nc] = true; st.push(new int[]{nr, nc});
}
}
}
shapes.add(canon(pts, T));
}
return shapes.size();
}
String canon(List<int[]> pts, int[][] T) {
String best = null;
for (int[] t : T) {
int sx = t[0], sy = t[1], sw = t[2];
List<int[]> r = new ArrayList<>();
for (int[] p : pts) r.add(sw == 1 ? new int[]{sx*p[1], sy*p[0]} : new int[]{sx*p[0], sy*p[1]});
r.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
int bx = r.get(0)[0], by = r.get(0)[1];
StringBuilder sb = new StringBuilder();
for (int[] p : r) sb.append(p[0] - bx).append(',').append(p[1] - by).append('|');
if (best == null || sb.toString().compareTo(best) < 0) best = sb.toString();
}
return best;
}int numDistinctIslands2(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<bool>> seen(m, vector<bool>(n, false));
set<string> shapes;
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int T[8][3] = {{1,1,0},{1,-1,0},{-1,1,0},{-1,-1,0},{1,1,1},{1,-1,1},{-1,1,1},{-1,-1,1}};
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (grid[r][c] == 1 && !seen[r][c]) {
vector<pair<int,int>> pts, st{{r, c}};
seen[r][c] = true;
while (!st.empty()) {
auto p = st.back(); st.pop_back(); pts.push_back(p);
for (auto& d : dirs) {
int nr = p.first + d[0], nc = p.second + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1 && !seen[nr][nc]) {
seen[nr][nc] = true; st.push_back({nr, nc});
}
}
}
string best; bool first = true;
for (auto& t : T) {
int sx = t[0], sy = t[1], sw = t[2];
vector<pair<int,int>> rr;
for (auto& p : pts) rr.push_back(sw ? make_pair(sx*p.second, sy*p.first) : make_pair(sx*p.first, sy*p.second));
sort(rr.begin(), rr.end());
int bx = rr[0].first, by = rr[0].second;
string s;
for (auto& p : rr) s += to_string(p.first - bx) + "," + to_string(p.second - by) + "|";
if (first || s < best) { best = s; first = false; }
}
shapes.insert(best);
}
return (int)shapes.size();
}Explanation
Two islands count as the same if one can be turned into the other by sliding, rotating, or flipping. The challenge is giving each island a canonical fingerprint so that all of its rotations and reflections produce the exact same string — then we just dedupe the fingerprints with a set.
First we grab each island's cells with a DFS that collects coordinates into pts. That gives the raw shape, but its fingerprint must not depend on orientation.
The canon function generates all 8 symmetries of a square (4 rotations × 2 reflections) using the sign/swap triples in T — e.g. (sx, sy, sw) flips axes and optionally swaps row/column. For each variant it sorts the points and shifts them so the smallest point sits at the origin, then it picks the lexicographically smallest of all 8 forms. Any island and its mirror image will both reduce to that same minimum form.
Example: a 4×5 grid holds island A and island B where B is a reflection of A. After canonicalization both collapse to the identical fingerprint, so the set holds just one entry and the answer is 1.
Counting distinct islands is then just len(shapes) — the number of unique canonical forms.