A possible solution using DFS:
def sink_island(r: int, c: int, grid: List[List[int]]) -> List[List[int]]:
grid[r][c] = 0
for delta_row, delta_column in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
neighbor_row = r + delta_row
neighbor_column = c + delta_column
if 0 <= neighbor_row < len(grid) and 0 <= neighbor_column < len(grid[0]):
if grid[neighbor_row][neighbor_column] == 1:
sink_island(neighbor_row, neighbor_column, grid)
return grid
def count_number_of_islands(grid: List[List[int]]) -> int:
res = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == 1:
sink_island(r, c, grid)
res += 1
return res
def get_neighbors(x, y, width, height):
for x_offset, y_offset in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
xi, yi = x + x_offset, y + y_offset
if 0 <= xi < width and 0 <= yi < height:
yield xi, yi
def count_number_of_islands(grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
island_num = 0
def dfs(x, y, visited, is_counted):
nonlocal island_num
if (x, y) in visited:
return
visited.add((x, y))
if grid[y][x] == 1:
if not is_counted:
island_num += 1
else:
return
for xi, yi in get_neighbors(x, y, width=len(grid[0]), height=len(grid)):
dfs(xi, yi, visited, True)
visited = set()
for j in range(len(grid)):
for i in range(len(grid[0])):
dfs(i, j, visited, False)
return island_num
I thought of the approach in the solution as well, but I was concerned the runtime would be O((mn)^2)?
The nested for-loop to traverse the matrix takes O(mn) time. We skip operations if matrix[r][c] == 0, but the traversal still takes O(mn) time.
Then at any one grid, the worst case flood fill takes O(mn) time. I’m thinking if a grid was full of 1’s.
Then at the 0th cell, it takes O(mn) time to flood fill the grid. And we still take O(mn) time to finish the nested for-loop.
Hmm i guess the situation I described is O( 2 * mn) = O(mn) but, idk
The official solution does not account for the visited locations. This is my version
def count_number_of_islands(grid: List[List[int]]) -> int:
num_of_islands = 0
visited = set()
def get_neighbors(location):
result = []
rows = [-1, 0, 1, 0]
cols = [0, 1, 0, -1]
for i in range(len(rows)):
rows_delta = rows[i] + location[0]
cols_delta = cols[i] + location[1]
if 0 <= rows_delta < len(grid) and 0 <= cols_delta < len(grid[0]):
result.append((rows_delta, cols_delta))
return result
def bfs(location, visited):
if location in visited:
return 0
island_found = 0
q = deque([location])
while q:
n = len(q)
for _ in range(n):
loc = q.popleft()
if grid[loc[0]][loc[1]] == 1:
island_found = 1
neighbors = get_neighbors(loc)
for neighbor in neighbors:
if neighbor in visited:
continue
visited.add(neighbor)
if grid[neighbor[0]][neighbor[1]] == 1:
q.append(neighbor)
return island_found
for i in range(len(grid)):
for j in range(len(grid[i])):
num_of_islands += bfs((i, j), visited)
return num_of_islands
Can someone help me understand the space complexity?