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

Code

from collections import deque

VISITED = "*"


def numIslands(grid: list[list[str]]) -> int:
    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

number_of_islands__bfs.numIslands(grid: list[list[str]]) → int