694. Number of Distinct Islands

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.

1
2
3
4

Example 1:

Input: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
Output: 1

ex1

1
2
3
4

Example 2:

Input: grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
Output: 3

ex2

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is either 0 or 1.

Set Solution

 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

class Solution {
    Set<Set<Pair<Integer, Integer>>> unique = new HashSet<>();
    public int numDistinctIslands(int[][] grid) {
        int count = 1;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    count++;
                    Set<Pair<Integer, Integer>> shape = new HashSet<>();
                    dfs(grid, i, j, shape, i, j, count);
                    unique.add(shape);
                }
            }
        }
        return unique.size();
    }
    
    int[][] DIRS = new int[][] {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    };
    
    void dfs(int[][] grid, int i, int j, Set<Pair<Integer, Integer>> shape, int start, int end, int index) {
        grid[i][j] = index;
        
        shape.add(new Pair(i - start, j - end));
        
        for (int[] dir: DIRS) {
            int x = dir[0] + i;
            int y = dir[1] + j;
            
            if (x < 0 || x == grid.length || y < 0 || y == grid[0].length) continue;
            
            if (grid[x][y] == 1) {
                dfs(grid, x, y, shape, start, end, index);
            }
        }
    }
}

Path Hash Solution

 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

class Solution {
    Set<String> unique = new HashSet<>();
    public int numDistinctIslands(int[][] grid) {
        int count = 1;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    count++;
                    StringBuilder sb = new StringBuilder();
                    dfs(grid, '0', i, j, sb, count);
                    unique.add(sb.toString());
                }
            }
        }
        return unique.size();
    }

    int[][] DIRS = new int[][] {
        {-1, 0}, // down 
        {0, 1}, // r
        {0, -1}, // l
        {1, 0}, // top
    };

    void dfs(int[][] grid, char direction, int i, int j, StringBuilder sb, int index) {
        if (i < 0 || i == grid.length || j < 0 || j == grid[0].length) return;
        if (grid[i][j] == 1) {
            grid[i][j] = index;
        
            sb.append(direction);

            dfs(grid, 'D', i + 1, j, sb, index);
            dfs(grid, 'T', i - 1, j, sb, index);
            dfs(grid, 'R', i, j + 1, sb, index);
            dfs(grid, 'L', i, j - 1, sb, index);
            sb.append('0');
        }
    }
}