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
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 num...read more
Top Expedia Group Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Top HR questions asked in Expedia Group Software Developer Intern
Reviews
Interviews
Salaries
Users/Month