Counting Islands

Question

You are given a 2-D grid where every cell holds one of two string characters: the character '1' marks land and the character '0' marks water. An island is a group of land cells connected to one another horizontally or vertically (4-directional adjacency, never diagonally), and the grid is surrounded by water on all sides. Count how many separate islands the grid contains.

def count_islands(grid: List[List[str]]) -> int:
    pass
Input


 	grid, a list of lists of the string characters '1' (land) and '0' (water). The grid may be empty.

Output


 	An integer: the number of islands (maximal connected groups of '1' cells under 4-directional adjacency).

Examples


 	grid = [['1','1','0','0'], ['1','1','0','0'], ['0','0','1','0'], ['0','0','0','1']] -> 3 (the 2x2 block top-left, the single cell in the middle, and the single cell bottom-right).
 	A grid that is entirely '0' -> 0.

Accepted Answer

Treat the grid as a graph whose vertices are the land cells and whose edges join 4-directionally adjacent land cells. Scan every cell once; when you meet an unvisited '1', it begins a new island, so bump the count and flood fill the whole connected blob (BFS here) to mark it visited. Each cell is enqueued and dequeued at most once, so the time is O(R x C) and the extra space is O(R x C) for the visited grid and queue, where R and C are the grid dimensions.

from collections import deque
from typing import List

def count_islands(grid: List[List[str]]) -> int:
    if not grid or not grid[0]:           # empty grid has no islands
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    count = 0

    for r in range(rows):
        for c in range(cols):
            # A fresh, unvisited land cell starts a brand-new island.
            if grid[r][c] == '1' and not visited[r][c]:
                count += 1
                # Flood fill this island with BFS, marking every reachable land cell.
                queue = deque([(r, c)])
                visited[r][c] = True
                while queue:
                    cr, cc = queue.popleft()
                    # 4-directional neighbors: down, up, right, left.
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nr, nc = cr + dr, cc + dc
                        if 0

Title	Category	Subcategory	Difficulty	Status
Course Schedule	Programming	Graphs	Hard	Unlock
Dijkstra's Algorithm #1	Programming	Graphs	Hard	Example
Dijkstra's Algorithm #2	Programming	Graphs	Hard	Unlock
Find All Paths	Programming	Graphs	Hard	Unlock
Minimum Spanning Tree (MST)	Programming	Graphs	Hard	Unlock

The Interview Guide for Quants and Traders

Counting Islands

What do you think of this page?