Number of Distinct Islands Leetcode Solution

Table of Contents

Problem Statement

The Number of Distinct Islands LeetCode Solution – “Number of Distinct Islands” states that given a n x m binary matrix. An island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical).

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.

We need to return a total number of distinct islands.

Example:

Input:  [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]

Output: 1

Explanation:

Check the above diagram for a better understanding.
Note that we cannot rotate or reflect the orientation of the island.
In the above figure, both the islands are identical, hence the number of distinct islands is 1.

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:

Check the above diagram for a better understanding.
Note that islands on the top right corner and bottom left corner are identical, while islands on the top left corner and bottom right corner are different.
Hence, the total number of distinct islands is 3.

Approach

Idea:

The main idea to solve this problem is to use Breadth-First Search.
Perform the Breadth-First Search in the matrix and find all the islands (connected components of 1’s).
How to find the count of islands? How to handle the case where two or more islands have the same shape?
1. Consider the set of coordinates that form the island.
2. Find the minimum x coordinate and minimum y coordinate among the set of coordinates, this coordinate will be the base coordinate for all the sets of coordinates constituting the island.
3. Find all the new coordinates for the current island with respect to the base coordinate.
4. Two or more islands have the same shape if they have the exact same set of coordinates with respect to their base coordinates.
Store all such array of coordinates in a Set, finally set size is our answer since a set will store all distinct sets of coordinates which is a set of all distinct islands.

Code

Number of Distinct Islands Leetcode C++ Solution:

class Solution {
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        int n = grid.size(),m = grid.back().size();
        vector<vector<bool>> vis(n,vector<bool>(m));
        set<vector<pair<int,int>>> distinct;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!grid[i][j]){
                    continue;
                }
                vector<pair<int,int>> coord;
                int mn_x = INT_MAX,mn_y = INT_MAX;
                queue<array<int,2>> q;
                q.push({i,j});
                grid[i][j] = 0;                
                while(!q.empty()){
                    int x = q.front()[0],y = q.front()[1];
                    q.pop();
                    mn_x = min(mn_x,x);
                    mn_y = min(mn_y,y);
                    coord.push_back({x,y});
                    for(int dx=-1;dx<=1;dx++){
                        for(int dy=-1;dy<=1;dy++){
                            int xx = x + dx,yy = y + dy;
                            if(xx<n and xx>=0 and yy<m and yy>=0 and abs(xx-x)+abs(yy-y)==1 and grid[xx][yy]==1){
                                q.push({xx,yy});
                                grid[xx][yy] = 0;
                            }
                        }
                    }
                }                
                for(auto& p:coord){
                    p.first-=mn_x;
                    p.second-=mn_y;
                }                
                sort(coord.begin(),coord.end());
                distinct.insert(coord);
            }
        }
        return distinct.size();
    }
};

Number of Distinct Islands Leetcode Java Solution:

class Solution {
    private int R[] = {0, 0, 1, -1};
    private int C[] = {1, -1, 0, 0};
    private int D[] = {1, 2, 3, 4};
    public int numDistinctIslands(int[][] grid) {
        Set<String> distinct = new HashSet<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    distinct.add(layout(i, j, grid));
                }
            }
        }
        return distinct.size();
    }
    private String layout(int i, int j, int grid[][]) {
        StringBuilder sb = new StringBuilder();
        Queue<int[]> queue = new LinkedList<>();
        int size, current[], nR, nC;
        queue.add(new int[] {i, j});
        while (!queue.isEmpty()) {
            size = queue.size();
            while (size != 0) {
                size--;
                current = queue.poll();
                for (int k = 0; k < R.length; k++) {
                    nR = current[0] + R[k];
                    nC = current[1] + C[k];
                    if (nR < 0 || nR == grid.length || nC < 0 || nC == grid[0].length || grid[nR][nC] != 1) {
                        sb.append(0);
                        continue;
                    }                    
                    if (grid[nR][nC] == 1) {
                        queue.add(new int[]{nR,nC});
                        grid[nR][nC] = 2;
                        sb.append(D[k]);
                    }
                }
            }
        }        
        return sb.toString();
    }
}

Complexity Analysis for Number of Distinct Islands Leetcode Solution

Time Complexity

The time complexity of the above code is O(N*Mlog(N*M)) since we consider cells of matrix and sorting the cells takes a logarithmic time.

Space Complexity

The space complexity of the above code is O(N*M) since we need a set to store the set of coordinates and in the worst case, it takes O(N*M) Space.