Number of distinct islands
December 24, 2022
graphProblem URL: Number of distinct islands
We will use a set to store the islands. We will iterate over the grid and call the dfs function on the current cell. We will return the result.
class Solution:
def numDistinctIslands(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
def dfs(r: int, c: int, area: str) -> str:
if r < 0 or r >= ROWS or c < 0 or c >= COLS or grid[r][c] == 0:
return '0'
grid[r][c] = 0
up = dfs(r-1, c, area)
down = dfs(r+1, c, area)
left = dfs(r, c-1, area)
right = dfs(r, c+1, area)
return up + down + left + right + '1'
res = set()
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 1:
res.add(dfs(r, c, '0'))
return len(res)
Time complexity: O(mn)
Space complexity: O(mn)