## Number of Distinct Islands II

• Time:O(mn\log(mn))
• Space:O(mn)

## C++

``````class Solution {
public:
int numDistinctIslands2(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
set<vector<pair<int, int>>> islands;  // all different shape islands
vector<vector<bool>> seen(m, vector<bool>(n));

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
vector<pair<int, int>> island;
dfs(grid, i, j, seen, island);
if (!island.empty())
islands.insert(normalize(island));
}

return islands.size();
}

private:
void dfs(const vector<vector<int>>& grid, int i, int j,
vector<vector<bool>>& seen, vector<pair<int, int>>& island) {
if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
return;
if (grid[i][j] == 0 || seen[i][j])
return;

seen[i][j] = true;
island.emplace_back(i, j);

dfs(grid, i + 1, j, seen, island);
dfs(grid, i - 1, j, seen, island);
dfs(grid, i, j + 1, seen, island);
dfs(grid, i, j - 1, seen, island);
}

vector<pair<int, int>> normalize(const vector<pair<int, int>>& island) {
// points[i] := 8 different rotations/reflections of island
vector<vector<pair<int, int>>> points(8);

for (const auto& [i, j] : island) {
points[0].emplace_back(i, j);
points[1].emplace_back(i, -j);
points[2].emplace_back(-i, j);
points[3].emplace_back(-i, -j);
points[4].emplace_back(j, i);
points[5].emplace_back(j, -i);
points[6].emplace_back(-j, i);
points[7].emplace_back(-j, -i);
}

for (vector<pair<int, int>>& p : points)
sort(begin(p), end(p));

// normalize each p by minus p[1:] w/ p[0]
for (vector<pair<int, int>>& p : points) {
for (int i = 1; i < island.size(); ++i)
p[i] = {p[i].first - p[0].first, p[i].second - p[0].second};
p[0] = {0, 0};
}

sort(begin(points), end(points));
return points[0];
}
};
``````

## JAVA

``````class Solution {
public int numDistinctIslands2(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
Set<List<Pair<Integer, Integer>>> islands = new HashSet<>(); // all different shape islands
boolean[][] seen = new boolean[m][n];

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
List<Pair<Integer, Integer>> island = new ArrayList<>();
dfs(grid, i, j, seen, island);
if (!island.isEmpty())
islands.add(normalize(island));
}

return islands.size();
}

private void dfs(int[][] grid, int i, int j, boolean[][] seen,
List<Pair<Integer, Integer>> island) {
if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
return;
if (grid[i][j] == 0 || seen[i][j])
return;

seen[i][j] = true;
island.add(new Pair<>(i, j));

dfs(grid, i + 1, j, seen, island);
dfs(grid, i - 1, j, seen, island);
dfs(grid, i, j + 1, seen, island);
dfs(grid, i, j - 1, seen, island);
}

private List<Pair<Integer, Integer>> normalize(List<Pair<Integer, Integer>> island) {
// points[i] := 8 different rotations/reflections of island
Pair<Integer, Integer>[][] points = new Pair[8][island.size()];

for (int k = 0; k < island.size(); ++k) {
final int i = island.get(k).getKey();
final int j = island.get(k).getValue();
points[0][k] = new Pair<>(i, j);
points[1][k] = new Pair<>(i, -j);
points[2][k] = new Pair<>(-i, j);
points[3][k] = new Pair<>(-i, -j);
points[4][k] = new Pair<>(j, i);
points[5][k] = new Pair<>(j, -i);
points[6][k] = new Pair<>(-j, i);
points[7][k] = new Pair<>(-j, -i);
}

for (Pair<Integer, Integer>[] p : points)
Arrays.sort(
p,
(a,
b) -> a.getKey() == b.getKey() ? a.getValue() - b.getValue() : a.getKey() - b.getKey());

// normalize each p by minus p[1:] w/ p[0]
for (Pair<Integer, Integer>[] p : points) {
for (int i = 1; i < island.size(); ++i)
p[i] = new Pair<>(p[i].getKey() - p[0].getKey(), p[i].getValue() - p[0].getValue());
p[0] = new Pair<>(0, 0);
}

Arrays.sort(points, new Comparator<Pair<Integer, Integer>[]>() {
@Override
public int compare(Pair<Integer, Integer>[] a, Pair<Integer, Integer>[] b) {
for (int i = 0; i < a.length; ++i) {
if (a[i].getKey() != b[i].getKey())
return a[i].getKey() - b[i].getKey();
if (a[i].getValue() != b[i].getValue())
return a[i].getValue() - b[i].getValue();
}
return 0;
}
});

return Arrays.asList(points[0]);
}
}
``````

## Python

``````class Solution:
def numDistinctIslands2(self, grid: List[List[int]]) -> int:
seen = set()

def dfs(i: int, j: int):
if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]):
return
if grid[i][j] == 0 or (i, j) in seen:
return

seen.add((i, j))
island.append((i, j))
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)

def normalize(island: List[tuple]) -> List[tuple]:
# points[i] := 8 different rotations/reflections of island
points = [[] for _ in range(8)]

for i, j in island:
points[0].append((i, j))
points[1].append((i, -j))
points[2].append((-i, j))
points[3].append((-i, -j))
points[4].append((j, i))
points[5].append((j, -i))
points[6].append((-j, i))
points[7].append((-j, -i))

points = [sorted(p) for p in points]

# normalize each p by minus p[1:] w/ p[0]
for p in points:
for i in range(1, len(island)):
p[i] = (p[i][0] - p[0][0],
p[i][1] - p[0][1])
p[0] = (0, 0)

return sorted(points)[0]

islands = set()  # all different shape islands

for i in range(len(grid)):
for j in range(len(grid[0])):
island = []
dfs(i, j)
if island:
islands.add(frozenset(normalize(island)))

return len(islands)
``````