Distinct Islands Problem Statement

Given a two-dimensional array/list consisting of integers 0s and 1s, where 1 represents land and 0 represents water, determine the number of distinct islands. A group of connected 1s (horizontally or vertically) forms an island.

Note:

Two islands are considered the same if one can be translated to overlap the other without rotation or reflection. If this condition is satisfied, they are considered identical.

Example:

Input:

1 1 0
0 0 1
0 0 1

Output:

2

Explanation:

Here, two islands exist and they cannot be translated to overlap each other, thus they are distinct.

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:

These islands can be translated to overlap each other, thus they are not distinct. Only one distinct island exists.

Input:

N, M

The first two numbers are the dimensions of the array: 'N' rows and 'M' columns.

The subsequent 'N' lines provide the values for each row, with each row containing 'M' space-separated values of the array.

Output:

Total number of distinct islands.

Constraints:

0 ≤ N ≤ 1000

0 ≤ M ≤ 1000

Array elements are either 0 or 1

Time Limit: 1 sec

Question

Distinct Islands Problem Statement

Given a two-dimensional array/list consisting of integers 0s and 1s, where 1 represents land and 0 represents water, determine the number of distinct islands. A group of connected 1s (horizontally or vertically) forms an island.

Note:

Two islands are considered the same if one can be translated to overlap the other without rotation or reflection. If this condition is satisfied, they are considered identical.

Example:

Input:

 1 1 0
 0 0 1
 0 0 1

Output:

Explanation:

Here, two islands exist and they cannot be translated to overlap each other, thus they are distinct.

Example:

Input:

Output:

Explanation:

These islands can be translated to overlap each other, thus they are not distinct. Only one distinct island exists.

Input:

N, M

The first two numbers are the dimensions of the array: 'N' rows and 'M' columns.

The subsequent 'N' lines provide the values for each row, with each row containing 'M' space-separated values of the array.

Output:

Total number of distinct islands.

Constraints:

0 ≤ N ≤ 1000
0 ≤ M ≤ 1000
Array elements are either 0 or 1
Time Limit: 1 sec

Accepted Answer

Count the number of distinct islands in a 2D array of 0s and 1s.

Identify connected groups of 1s to form islands
Check if islands can be translated to overlap without rotation or reflection
Count the number of distinct islands based on the above criteria