Distinct Islands
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.

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

Question

Distinct Islands

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.

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

Accepted Answer

I used Depth-first search to determine connected components.

Accepted Answer

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.

Space Complexity: O(m*n) - For 2d arraysExplanation:

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).

Time Complexity: O(m*n) - For 2d arraysExplanation:

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)