05 August 2008
You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.
Return the number of distinct islands.
Brute Force - O(M^2 * N^2).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
private List<List<int[]>> uniqueIslands = new ArrayList<>(); // All known unique islands.
private List<int[]> currentIsland = new ArrayList<>(); // Current Island
private int[][] grid; // Input grid
private boolean[][] seen; // Cells that have been explored.
public int numDistinctIslands(int[][] grid) {
this.grid = grid;
this.seen = new boolean[grid.length][grid[0].length];
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
dfs(row, col);
if (currentIsland.isEmpty()) {
continue;
}
// Translate the island we just found to the top left.
int minCol = grid[0].length - 1;
for (int i = 0; i < currentIsland.size(); i++) {
minCol = Math.min(minCol, currentIsland.get(i)[1]);
}
for (int[] cell : currentIsland) {
cell[0] -= row;
cell[1] -= minCol;
}
// If this island is unique, add it to the list.
if (currentIslandUnique()) {
uniqueIslands.add(currentIsland);
}
currentIsland = new ArrayList<>();
}
}
return uniqueIslands.size();
}
private void dfs(int row, int col) {
if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length) return;
if (seen[row][col] || grid[row][col] == 0) return;
seen[row][col] = true;
currentIsland.add(new int[]{row, col});
dfs(row + 1, col);
dfs(row - 1, col);
dfs(row, col + 1);
dfs(row, col - 1);
}
private boolean currentIslandUnique() {
for (List<int[]> otherIsland : uniqueIslands) {
if (currentIsland.size() != otherIsland.size()) continue;
if (equalIslands(currentIsland, otherIsland)) {
return false;
}
}
return true;
}
private boolean equalIslands(List<int[]> island1, List<int[]> island2) {
for (int i = 0; i < island1.size(); i++) {
if (island1.get(i)[0] != island2.get(i)[0] || island1.get(i)[1] != island2.get(i)[1]) {
return false;
}
}
return true;
}
}
Hash By Local Coordinates - O(M⋅N).
The best way of implementing this is language-dependent.
In Java, we can actually represent each island as a HashSet of Pairs, with one Pair for each cell. We can then put all of the islands into another HashSet, and this will hash the HashSets that represent the islands.
In Python, there is a data structure called a frozenset that we have to use instead, as unlike Java, Python doesn’t allow inserting a set into another set. A frozenset is an immutable set.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
private int[][] grid;
private boolean[][] seen;
private Set<Pair<Integer, Integer>> currentIsland;
private int currRowOrigin;
private int currColOrigin;
private void dfs(int row, int col) {
if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length) return;
if (grid[row][col] == 0 || seen[row][col]) return;
seen[row][col] = true;
currentIsland.add(new Pair<>(row - currRowOrigin, col - currColOrigin));
dfs(row + 1, col);
dfs(row - 1, col);
dfs(row, col + 1);
dfs(row, col - 1);
}
public int numDistinctIslands(int[][] grid) {
this.grid = grid;
this.seen = new boolean[grid.length][grid[0].length];
Set<Set<Pair<Integer, Integer>>> islands = new HashSet<>();
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
this.currentIsland = new HashSet<>();
this.currRowOrigin = row;
this.currColOrigin = col;
dfs(row, col);
if (!currentIsland.isEmpty()) islands.add(currentIsland);
}
}
return islands.size();
}
}