Number of Islands

Problem statement

You get a 2D grid of '1' (land) and '0' (water). An island is a maximal group of land cells connected in four directions (up, down, left, right — no diagonals). Return how many islands are in the grid.

Example:

Input:

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Expected output:

3

Practice on LeetCode: Number of Islands

Golang Solution

Scan every cell. When you find unvisited land, increment the island count and DFS to mark the whole connected component visited before continuing the scan.

Time: O(m · n) — each cell processed a constant number of times
Space: O(m · n) — visited matrix and recursion stack in the worst case

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    visited := make([][]int, len(grid))

    for i := 0; i < len(grid); i++ {
        visited[i] = make([]int, len(grid[0]))
    }

    count := 0

    var dfs func(i, j int)

    dfs = func(i, j int) {
        // Out of bounds
        if i < 0 || i >= len(grid) ||
            j < 0 || j >= len(grid[0]) {
            return
        }

        // Water or already visited
        if grid[i][j] == '0' || visited[i][j] == 1 {
            return
        }

        // Mark visited
        visited[i][j] = 1

        // Explore four directions
        dfs(i-1, j) // up
        dfs(i+1, j) // down
        dfs(i, j-1) // left
        dfs(i, j+1) // right
    }

    // Find every new island
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' && visited[i][j] == 0 {
                count++
                dfs(i, j)
            }
        }
    }

    return count
}