Number of distinct islands
Kotak
OracleThe problem
You are given a 2D matrix grid of size N × M, where each cell contains either 0 or 1. Find the number of distinct islands where a group of connected 1s (horizontally or vertically) forms an island. Two islands are considered to be same if and only if one island is equal to another (not rotated or reflected).
Input: grid = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 1],[0, 0, 0, 1, 1]] Output: 1 Explanation:
Same colored islands are equal. We have 2 equal islands, so we have only 1 distinct island.
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:
Same colored islands are equal. We have 4 islands, but 2 of them are equal, So we have 3 distinct islands..
Input: grid = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0],[0, 0, 0, 1, 1]]
- 1 <= N, M <= 500
- grid[i][j] == 0 or 1
cpp
class Solution
{
public:
int countDistinctIslands(vector<vector<int>> &grid){
}
};java
class Solution {
public int countDistinctIslands(int[][] grid) {
}
}python
class Solution:
def countDistinctIslands(self, grid):javascript
class Solution {
countDistinctIslands(grid) {
}
}csharp
public class Solution
{
public int CountDistinctIslands(List<List<int>> grid)
{
}
}go
func countDistinctIslands(grid [][]int) int {
}Stuck? Show a way to structure it+
- 01Scan the grid for unvisited land
- 02DFS each island while collecting relative coordinates
- 03Serialize the ordered relative shape consistently
- 04Insert the signature into a set
Reference answer
Then expect these follow-ups
How do you treat rotations as identical?
Tests: follow-up reasoning
Can BFS be used instead of DFS?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question