Leetcode 200 Number of Islands
https://leetcode.com/problems/number-of-islands/description
This is a classic problem that uses BFS as solution.
The idea is, we analyze every cell in the grid, if it’s land and we have never visited it before, we find a new island. But we need to keep going from this cell and find all the connected land and mark them as visited so we don’t have to check it again.
When we check neighbors for a particular cell, only if it’s land we put it in the queue. Once the queue is empty, it means the whole island is found and we should move out of the current bfs. Don’t forget the mark the neighbor as visited!
Let’s take a look at the solution
class Solution:
def bfs(self, m, n, visited, grid):
queue = collections.deque()
queue.append((m, n))
deltas = [(-1, 0), (1, 0), (0, 1), (0, -1)]
while queue:
x, y = queue.popleft()
for delta in deltas:
x_delta, y_delta = delta
if (x + x_delta) in range(len(grid)) and (y + y_delta) in range(len(grid[0])) and grid[x + x_delta][y + y_delta] == "1" and (x + x_delta, y + y_delta) not in visited:
queue.append((x + x_delta, y + y_delta))
visited.add((x + x_delta, y + y_delta))
def numIslands(self, grid: List[List[str]]) -> int:
if len(grid) == 0 or len(grid[0]) == 0:
return -1
count = 0
visited = set()
for m in range(len(grid)):
for n in range(len(grid[0])):
if (m, n) not in visited and grid[m][n] == "1":
count += 1
self.bfs(m, n, visited, grid)
return count
The time complexity is O(nm) since we iterate the whole grid.
Pingback: Breadth First Search(BFS) - Leetcode Solution