#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/flood-fill-grid-graphs/number-of-islands-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/flood-fill-grid-graphs/number-of-islands-implementation

Repovive

LeetCode 200 Number of Islands - Implementation - Flood Fill & Grid Graphs | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

LeetCode 200 Number of Islands - Implementation

Coding the Sinking Strategy

Here is the solution:

function eraseIsland(grid, r, c):
    if r < 0 or c < 0 or r >= rows or c >= cols:
        return
    if grid[r][c] == '0':
        return

    grid[r][c] = '0'  // Sink it

    eraseIsland(grid, r + 1, c)
    eraseIsland(grid, r - 1, c)
    eraseIsland(grid, r, c + 1)
    eraseIsland(grid, r, c - 1)

function numIslands(grid):
    count = 0
    for i from 0 to rows - 1:
        for j from 0 to cols - 1:
            if grid[i][j] == '1':
                count = count + 1
                eraseIsland(grid, i, j)
    return count

This runs in $O(m \times n)$ time and uses $O(m \times n)$ space.