Number of Islands

Problem

https://leetcode.com/problems/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.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

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

Pattern

Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Approaches

BFS

Explanation

To count the number of islands, we can count the number of times we encounter a land cell. When we encounter a land cell, we can perform a BFS to mark all the land cells connected to it (the island) as visited (-1). This way, we won’t count the same island multiple times. We can use BFS to visit all the land cells in an island.

Code

from collections import deque

VISITED = "*"


def numIslands(grid: list[list[str]]) -> int:
    """Given an 2D binary ``grid`` which represents a map of ``'1'``s (land)
    and ``'0'``s (water), return the number of islands.
    """
    M = len(grid)
    N = len(grid[0])

    def bfs(start_i, start_j):
        queue = deque()

        queue.append((start_i, start_j))
        while queue:
            i, j = queue.popleft()

            if not (0 <= i < M and 0 <= j < N):
                continue

            if grid[i][j] == VISITED or grid[i][j] == "0":
                continue

            if grid[i][j] == "1":
                grid[i][j] = VISITED
                queue.append((i + 1, j))
                queue.append((i - 1, j))
                queue.append((i, j + 1))
                queue.append((i, j - 1))

    result = 0
    for i in range(M):
        for j in range(N):
            if grid[i][j] == "1":
                result += 1
                bfs(i, j)

    return result

Test

>>> from number_of_islands__bfs import numIslands
>>> numIslands([["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]])
1
>>> numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]])
3

Complexity

Measure	Complexity	Notes
Time	\(O(mn)\)	visit every cell in the grid
Auxiliary Space	\(O(\sqrt{m^2 + n^2})\)	worst case entire grid is one island; the maximum size of the queue will be the diagonal of the grid (\(\sqrt{m^2 + n^2} \leq m + n\))

number_of_islands__bfs.numIslands(grid: list[list[str]]) → int: Given an 2D binary grid which represents a map of ``’1’``s (land) and ``’0’``s (water), return the number of islands.