MediumBlind75MatrixDFSBFSUnion Find

Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

Examples

Input
grid = [['1','1','1','1','0'],['1','1','0','1','0'],['1','1','0','0','0'],['0','0','0','0','0']]
Output
1

There is one island consisting of connected land cells.

Input
grid = [['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]
Output
3

There are 3 separate islands.

Constraints

  • •m == grid.length
  • •n == grid[i].length
  • •1 <= m, n <= 300
  • •grid[i][j] is '0' or '1'.

Approaches

For each unvisited land cell, start DFS to mark all connected land.

CodeT: O(m * n) | S: O(m * n)
def num_islands(grid):
    if not grid:
        return 0
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                count += 1
                dfs(grid, i, j)
    return count

def dfs(grid, i, j):
    if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
        return
    grid[i][j] = '0'
    dfs(grid, i + 1, j)
    dfs(grid, i - 1, j)
    dfs(grid, i, j + 1)
    dfs(grid, i, j - 1)

Use BFS to explore all connected land cells.

CodeT: O(m * n) | S: O(min(m, n))
from collections import deque

def num_islands(grid):
    if not grid:
        return 0
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                count += 1
                grid[i][j] = '0'
                queue = deque([(i, j)])
                while queue:
                    x, y = queue.popleft()
                    for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == '1':
                            grid[nx][ny] = '0'
                            queue.append((nx, ny))
    return count

Use Union Find data structure to count connected components.

Diagram

grid = [['1','1','0'],['0','1','0'],['0','0','1']] Islands: cell(0,0)-(0,1)-(1,1) connected, cell(2,2) separate Count = 2
CodeT: O(m * n * alpha(m*n)) | S: O(m * n)
class UnionFind:
    def __init__(self, grid):
        self.parent = []
        self.rank = []
        self.count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.parent.append(i * len(grid[0]) + j)
                    self.count += 1
                else:
                    self.parent.append(-1)
                self.rank.append(0)
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1

def num_islands(grid):
    if not grid:
        return 0
    uf = UnionFind(grid)
    rows, cols = len(grid), len(grid[0])
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                if i + 1 < rows and grid[i+1][j] == '1':
                    uf.union(i * cols + j, (i+1) * cols + j)
                if j + 1 < cols and grid[i][j+1] == '1':
                    uf.union(i * cols + j, i * cols + j + 1)
    return uf.count

Complexity Comparison

Brute Force - DFS per Cell
T: O(m * n)S: O(m * n)

For each unvisited land cell, start DFS to mark all connected land.

BFS
T: O(m * n)S: O(min(m, n))

Use BFS to explore all connected land cells.

Union Find
T: O(m * n * alpha(m*n))S: O(m * n)

Use Union Find data structure to count connected components.

Common Mistakes

Modifying the grid without restoring it (if not allowed)

Not checking all four directions (up, down, left, right)

Using DFS recursion that may cause stack overflow for large grids

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems