Number of Distinct Islands

Problem

Given a boolean 2D matrix grid of size n * m. You have to find the number of distinct islands where a group of connected 1s (horizontally or vertically) forms an island. Two islands are considered to be distinct if and only if one island is not equal to another (not rotated or reflected). (link)

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
Explanation:
grid[][] = [[1, 1, 0, 0, 0], 
            [1, 1, 0, 0, 0], 
            [0, 0, 0, 1, 1], 
            [0, 0, 0, 1, 1]]
Same colored islands are equal.
We have 2 equal islands, so we 
have only 1 distinct island.

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
Explanation:
grid[][] = [[1, 1, 0, 1, 1], 
            [1, 0, 0, 0, 0], 
            [0, 0, 0, 0, 1], 
            [1, 1, 0, 1, 1]]
Same colored islands are equal.
We have 4 islands, but 2 of them
are equal, So we have 3 distinct islands.

Constraints:
1 ≤ n, m ≤ 500
grid[i][j] == 0 or grid[i][j] == 1

Solution

Idea: If we have two islands with exactly the same structure, then the DFS/BFS traversal of these islands will also be identical.

We use a set to store all the islands and return the size of the set, as it contains only distinct elements.

Note: The set will contain elements that are lists of strings. The set uses the default equals and hash methods of the list to identify distinct elements.

• To match the structure of the islands, we store their indices. If the indices match, then the two islands are the same. We normalize the indices to (0,0) so we can easily compare the structures of two islands.

• We normalize the coordinates by subtracting the root or starting indices from all the coordinates.

Time - O(nxm) + O(nxmx4) + O(log(nxm))

Space - O(nxm)

class Solution {

    void dfs(int i, int j, int[][] grid, int[][] visited, List<String> island, int row0, int col0){
        if(!isValid(i, j, grid, visited)){
            return;
        }

        visited[i][j] = 1;
        island.add(toString(i-row0, j-col0));
        dfs(i-1,j,grid,visited,island, row0, col0);
        dfs(i+1,j,grid,visited,island, row0, col0);
        dfs(i,j-1,grid,visited,island, row0, col0);
        dfs(i,j+1,grid,visited,island, row0, col0);
    }    

    boolean isValid(int i, int j, int[][] grid, int[][] visited){
        int m = grid.length;
        int n = grid[0].length;

        if(i<0 || i>=m) return false;
        if(j<0 || j>=n) return false;

        if(visited[i][j]==1) return false;

        if(grid[i][j]!=1) return false;

        return true;
    }

    String toString(int rowDiff, int colDiff) {
        return "(" + rowDiff + ", " + colDiff + ")";
    }

    int countDistinctIslands(int[][] grid) {
        Set<List<String>> set = new HashSet<>();

        int m = grid.length;
        int n = grid[0].length;

        int[][] visited = new int[m][n];

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){

                if(grid[i][j] == 1 && visited[i][j]!=1){
                    List<String> island = new ArrayList<>();
                    dfs(i, j, grid, visited, island, i, j);
                    set.add(island);
                }
            }
        }
        return set.size();
    }
}