Dev Skills
Go·Go for coding rounds

Number of islands: DFS on a grid

A grid is a graph in disguise. Find unvisited land, flood it, count one.

Topic 36 of 98 · 5 min to read · 45 min to build
After this topic you can
  • Write a flood fill that counts islands in a grid.
  • Fix out-of-range panics by bounds-checking before indexing.
  • Predict the island count for a small grid.

The problem

Given a grid of '1' (land) and '0' (water), count the islands. An island is land cells joined up, down, left or right.

Brute force first

Without marking cells: for every land cell, check whether it already belongs to an island you have found (by scanning a list of stored islands). If not, collect its whole island and store it.

Each check scans everything found so far: O((rows·cols)²) time, O(rows·cols) space. Marking cells as you sink them removes that repeated search.

The approach

Scan every cell. When you find land, count one island and flood-fill it: visit it, mark it, then visit its four neighbours. Marked cells are never counted again. O(rows · cols) time, and O(rows · cols) stack in the worst case.

For a huge grid, swap the recursion for a slice queue (BFS) so you cannot run out of stack. The counting logic does not change.

islands.go
package main
import "fmt"
// numIslands counts groups of '1' cells joined up, down, left or right.
// Each time we find unvisited land, we sink the whole island with DFS.
func numIslands(grid [][]byte) int {
	rows := len(grid)
	if rows == 0 {
		return 0
	}
	cols := len(grid[0])
	var sink func(r, c int)
	sink = func(r, c int) {
		if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1' {
			return // bounds check first, or grid[r][c] panics
		}
		grid[r][c] = '0' // mark visited by changing the grid itself
		sink(r+1, c)
		sink(r-1, c)
		sink(r, c+1)
		sink(r, c-1)
	}
	count := 0
	for r := range grid {
		for c := range grid[r] {
			if grid[r][c] == '1' {
				count++
				sink(r, c)
			}
		}
	}
	return count
}
func parse(lines ...string) [][]byte {
	g := make([][]byte, len(lines))
	for i, l := range lines {
		g[i] = []byte(l)
	}
	return g
}
func main() {
	fmt.Println(numIslands(parse(
		"11000",
		"11000",
		"00100",
		"00011",
	))) // 3
	fmt.Println(numIslands(parse("111", "010", "111"))) // 1
}

Dry run

The grid from the program, scanning row by row:

cell foundcountsink marks
(0,0) land1(0,0) (0,1) (1,0) (1,1)
(0,1) (1,0) (1,1)1already 0, skipped
(2,2) land2(2,2)
(3,3) land3(3,3) (3,4)
end of scan3answer: 3

Go-specific gotchas

  • Bounds check before you index. grid[r][c] with r = -1 panics. Put all four bound checks first in the same if.
  • Mark visited cells, here by writing '0' into the grid. If you must not change the input, use a separate [][]bool. Ask which they want.
  • `'1'` is a byte (rune literal), `"1"` is a string. Comparing a byte cell with "1" does not compile.
  • Go stacks grow, so deep recursion rarely crashes. It is still slower than a loop for very large grids.
The short version
  • Each cell is a node; its four neighbours are its edges.
  • Count when you find unvisited land, then flood it.
  • Bounds check first, then mark visited.
Remember: Any "count the connected groups" question is a flood fill.
Build this before moving on
Return the area of the largest island instead of the count. Make sink return how many cells it covered.
Coding challenge · checked by tests
Online-assessment style islands. Write Solve(r io.Reader, w io.Writer). The input is T, then T grids; each grid is rows cols followed by rows lines of 0 and 1 (no spaces inside a line). For each grid print how many islands of 1s it has, where cells join only up, down, left and right (not diagonally). Example: "1\n2 2\n10\n01\n" → "2\n".

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Return the area of the largest island instead of the count. Make sink return how many cells it covered.
  2. 2Dry run numIslands on the 3×3 grid 101 / 010 / 101. What is the answer, and would it change if diagonals counted?
  3. 3Count the cells of water that touch at least one land cell (up, down, left or right).
Official documentation
Check yourselfTake the Go for coding rounds test