Problem Description

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.

Problem Link

Solution 1: DFS

Use recursive DFS to explore and mark all connected land cells when we encounter an unvisited ‘1’.

Steps

1. Iterate through the grid: Scan each cell in the 2D grid
2. Detect new island: When we find a ‘1’ (unvisited land), increment the island counter
3. Mark entire island: Use DFS to recursively visit all connected land cells
4. Mark as visited: Change ‘1’ to ‘0’ to avoid revisiting the same land
5. Explore four directions: From each land cell, recursively check up, down, left, right

Code

func numIslands(grid [][]byte) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }
    res := 0
    for i:=0; i < len(grid); i++ {
        for j:=0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                res++
                dfs(grid, i, j)
            }
        }
    }
    return res
}

func dfs(grid[][] byte, x, y int) {
    if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[0]) {
        return
    }
    if grid[x][y] == '1' {
        grid[x][y] = '0'
        dfs(grid, x+1, y)
        dfs(grid, x-1, y)
        dfs(grid, x, y+1)
        dfs(grid, x, y-1)
    }
}

Time Complexity: O(m*n)

Space Complexity: O(m*n)

Solution 2 : Union Find

Model each land cell as a node and connect adjacent land cells. Count the number of distinct connected components using Union-Find data structure.

Steps

1. Initialize Union-Find: Create parent array where each cell is its own parent
2. Map 2D to 1D: Convert (i,j) coordinates to single index: i * cols + j
3. Connect adjacent lands: For each ‘1’, union it with adjacent ‘1’ cells
4. Count land cells: Track total number of land cells initially
5. Union operations: Each successful union reduces component count by 1
6. Return components: Final count represents number of islands

Code

type UnionFind struct {
    parent []int
    rank []int
    count int
}

func NewUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    rank := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
        rank[i] = 0
    }
    return &UnionFind{
        parent: parent,
        rank: rank,
        count: 0,
    }
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
    rootX := uf.Find(x)
    rootY := uf.Find(y)

    if rootX != rootY {
        if uf.rank[rootX] < uf.rank[rootY] {
            uf.parent[rootX] = rootY
        } else if uf.rank[rootX] > uf.rank[rootY] {
            uf.parent[rootY] = rootX
        } else {
            uf.parent[rootY] = rootX
            uf.rank[rootX]++
        }
        uf.count--
    }
    
}


func (uf *UnionFind) GetCount() int {
    return uf.count
}

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

    rows, cols := len(grid), len(grid[0])
    uf := NewUnionFind(rows*cols)

    getIndex := func(i, j int) int {
        return i * cols + j
    }

    landCount := 0

    for i :=0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == '1' {
                landCount++
            }
        }
    }
    uf.count = landCount

    directions := [][]int{{-1,0},{1,0}, {0,1}, {0,-1}}

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == '1' {
                for _, dir := range directions {
                    ni, nj := i+dir[0], j+dir[1]
                    if ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] == '1' {
                        uf.Union(getIndex(i,j), getIndex(ni, nj))
                    }

                }
            }
        }
    }
    return uf.GetCount()
}

Time Complexity: O(m*n)

Space Complexity: O(m*n)

Solution 3 : BFS

Use a queue to perform level-by-level traversal of connected land cells, exploring all neighbors before moving to the next level.

Steps

1. Iterate through the grid: Scan each cell to find unvisited land
2. Initialize BFS: When finding a ‘1’, add it to queue and mark as visited
3. Level-by-level exploration: Process all cells in current level before next level
4. Expand to neighbors: For each cell in queue, check its four adjacent cells
5. Add new lands to queue: If adjacent cell is unvisited land, add to queue
6. Continue until queue empty: Complete exploration of one connected component

Code

type Point struct {
	x, y int
}

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

	rows, cols := len(grid), len(grid[0])
	count := 0

	directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

	bfs := func(startX, startY int) {
		queue := []Point{{startX, startY}}
		grid[startX][startY] = '0'

		for len(queue) > 0 {
			current := queue[0]
			queue = queue[1:]

			for _, dir := range directions {
				newX := current.x + dir[0]
				newY := current.y + dir[1]

				if newX >= 0 && newX < rows &&
					newY >= 0 && newY < cols &&
					grid[newX][newY] == '1' {

					grid[newX][newY] = '0'
					queue = append(queue, Point{newX, newY})
				}
			}
		}
	}

	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if grid[i][j] == '1' {
				count++
				bfs(i, j)
			}
		}
	}

	return count
}

Time Complexity: O(m*n)

Space Complexity: O(min(m,n))