Distinct Islands

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
113 upvotes
Asked in companies
SalesforceExpedia GroupMicrosoft

Problem statement

You are given a two-dimensional array/list of integers consisting of 0s and 1s. In the list, 1 represents land and 0 represents water.

The task is to find the number of distinct islands where a group of connected 1s(horizontally or vertically) forms an island.

Note: 
Two islands are considered to be the same if and only if one island is equal to another(not rotated or reflected) i.e if we can translate one island on another without rotating or reflecting then it would be considered as the same islands.
For example: 
1 1 0
0 0 1
0 0 1

In this example, we have two islands and they would be considered as distinct islands as we can not translate them on one another even if they have the same no of 1's.
For example : 
1 1 0 0 0 
1 1 0 0 0
0 0 0 1 1
0 0 0 1 1

In this example, we have two islands and they are the same as we can translate one island onto another island, so our answer should be 1.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first two lines contain two integer values, 'N' and 'M'. They represent the 'rows' and 'columns' respectively, for the two-dimensional array/list.

From the third line onwards, the next 'N' lines or rows represent the i-th row values.

Each of the i-th rows contains 'M' column values separated by a single space.
Output format: 
The only line of output contains the total number of distinct Islands.
Constraints 
 0 <= N <= 1000
 0 <= M <= 1000
 0 <= elements of array <= 1

Time Limit: 1 sec
Sample Input 1:
 4
 5
 1 1 0 1 1
 1 0 0 0 0
 0 0 0 0 1
 1 1 0 1 1
Sample Output 1:
 3
Explanation For Sample Input 1:
Distinct islands in the example above are: 

1st -> at the top left corner; 

2nd -> at the top right corner  

3rd -> at the bottom right corner. 

We ignore the island at the bottom left corner since it is identical to the top right corner.
Sample Input 2:
3
2
1 0
0 1
1 1
Sample Output 2:
2
Hint

Find the total number of unique connected components.

Approaches (1)
Depth First Search
  • For every 1 in the matrix, do DFS and mark all the 1’s as visited which are connected to this 1 and store the path of the island in a string.

  

     Followings are the abbreviated path :

     ‘S’ - starting vertex

     ‘D’ - down

     ‘U’ - up

     ‘L’ - left

     ‘R’ - right

     ‘B’ - backtrack

 

Consider the following island:

1 1
1 0

 

Let us simulate the solution's algorithm on this island to understand its working:

 

At cell (0,0), path = “S”.

We move right.

 

At cell (0,1), path = “SR”.

We cannot go further, hence we backtrack.

 

At cell (0,0), path = “SRB”.

We move down.

 

At cell (1,0), path = “SRBD”.

We cannot go further, hence we backtrack.

 

At cell (0,0), path = “SRBDB”.

We cannot go further, hence we terminate.

 

Final path = “SRBDB”.

 

  • For every connected component store the path in the set.

 

  • Finally, the size of the set will be the total number of distinct islands.
Time Complexity

O(N * M), Where N and M are the rows and columns of the matrix.

 

Since in the worst case we would be traversing through the complete matrix that takes O(N * M) time. Hence the overall time complexity is O(N * M)

Space Complexity

O(N * M), where N and M are the rows and columns of the matrix. 

 

Since we are using string to store paths that take O(N * M) space. Hence the overall space complexity is O(N * M).

Code Solution
(100% EXP penalty)
Distinct Islands
Full screen
Console