Number of Islands
Problem Statement
Given a 2D grid grid
where '1'
represents land and '0'
represents water, count and return the number of islands.
An island is formed by connecting adjacent lands horizontally or vertically and is surrounded by water. You may assume water is surrounding the grid (i.e., all the edges are water).
Example 1:
Input: grid = [ ["0","1","1","1","0"], ["0","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]Output: 1
Example 2:
Input: grid = [ ["1","1","0","0","1"], ["1","1","0","0","1"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]Output: 4
Constraints:
1 <= grid.length, grid[i].length <= 100
grid[i][j]
is'0'
or'1'
.
You should aim for a solution with O(m * n)
time and O(m * n)
space, where m
is the number of rows and n
is the number of columns in the grid.
Recommended Time and Space Complexity
You should aim for a solution with O(m * n)
time and O(m * n)
space, where m
is the number of rows and n
is the number of columns in the grid.
Hint 1
An island is a group of 1
’s in which every 1
is reachable from any other 1
in that group. Can you think of an algorithm that can find the number of groups by visiting a group only once? Maybe there is a recursive way of doing it.
Hint 2
We can use the Depth First Search (DFS) algorithm to traverse each group independently. We iterate through each cell of the grid. When we encounter a 1
, we perform a DFS starting at that cell and recursively visit every other 1
that is reachable. During this process, we mark the visited 1
’s as 0
to ensure we don’t revisit them, as they belong to the same group. The number of groups corresponds to the number of islands.
Solution
Depth First Search
def num_islands_dfs(grid: List[List[str]]) -> int: directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] rows, cols = len(grid), len(grid[0]) islands = 0
def dfs(r, c): if (r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == "0" ): return
grid[r][c] = "0" for dr, dc in directions: dfs(r + dr, c + dc)
for r in range(rows): for c in range(cols): if grid[r][c] == "1": dfs(r, c) islands += 1
return islands
Time complexity: O(m * n)
Space complexity: O(m * n)
Breadth First Search
from collections import deque
def num_islands_bfs(grid: List[List[str]]) -> int: directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] rows, cols = len(grid), len(grid[0]) islands = 0
def bfs(r, c): q = deque() grid[r][c] = "0" q.append((r, c))
while q: row, col = q.popleft() for dr, dc in directions: nr, nc = dr + row, dc + col if (nr < 0 or nc < 0 or nr >= rows or nc >= cols or grid[nr][nc] == "0" ): continue q.append((nr, nc)) grid[nr][nc] = "0"
for r in range(rows): for c in range(cols): if grid[r][c] == "1": bfs(r, c) islands += 1
return islands
Time complexity: O(m * n)
Space complexity: O(m * n)
Disjoint Set Union
class DisjointSetUnion: def __init__(self, n): self.parent = list(range(n + 1)) self.size = [1] * (n + 1)
def find(self, node): if self.parent[node] != node: self.parent[node] = self.find(self.parent[node]) return self.parent[node]
def union(self, u, v): parent_u = self.find(u) parent_v = self.find(v) if parent_u == parent_v: return False if self.size[parent_u] >= self.size[parent_v]: self.size[parent_u] += self.size[parent_v] self.parent[parent_v] = parent_u else: self.size[parent_v] += self.size[parent_u] self.parent[parent_u] = parent_v return True
def num_islands_dsu(grid: List[List[str]]) -> int: rows, cols = len(grid), len(grid[0]) dsu = DisjointSetUnion(rows * cols)
def index(r, c): return r * cols + c
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] islands = 0
for r in range(rows): for c in range(cols): if grid[r][c] == '1': islands += 1 for dr, dc in directions: nr, nc = r + dr, c + dc if (nr < 0 or nc < 0 or nr >= rows or nc >= cols or grid[nr][nc] == "0" ): continue
if dsu.union(index(r, c), index(nr, nc)): islands -= 1
return islands
Time complexity: O(m * n)
Space complexity: O(m * n)