Number of Islands BFS and DFS in DSA Go

Mental Model

We find groups of connected land cells by exploring neighbors until no new land is found. Each group is one island.

Analogy: Imagine walking through a forest and marking all trees connected by paths as one cluster before moving to the next cluster.

Grid example:
1 1 0 0 0
1 1 0 0 1
0 0 0 1 1
0 0 0 0 0
1 0 1 0 1

1 = land, 0 = water

Dry Run Walkthrough

Input: grid: [[1,1,0,0,0],[1,1,0,0,1],[0,0,0,1,1],[0,0,0,0,0],[1,0,1,0,1]]

Goal: Count how many separate islands (groups of connected 1s) are in the grid

Step 1: Start at top-left cell (0,0), find land, begin BFS/DFS to mark connected land

Visited cells marked: (0,0), (0,1), (1,0), (1,1)
Grid with visited: 
X X 0 0 0
X X 0 0 1
0 0 0 1 1
0 0 0 0 0
1 0 1 0 1

Why: We found the first island by exploring all connected land cells

Step 2: Move to cell (1,4), find unvisited land, start BFS/DFS to mark connected land

Visited cells marked: (1,4), (2,3), (2,4)
Grid with visited: 
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
1 0 1 0 1

Why: Second island found by exploring connected land cells in this area

Step 3: Move to cell (4,0), find unvisited land, mark it as island 3

Visited cells marked: (4,0)
Grid with visited: 
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 1 0 1

Why: Third island is a single land cell isolated from others

Step 4: Move to cell (4,2), find unvisited land, mark it as island 4

Visited cells marked: (4,2)
Grid with visited: 
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 X 0 1

Why: Fourth island is another isolated land cell

Step 5: Move to cell (4,4), find unvisited land, mark it as island 5

Visited cells marked: (4,4)
Grid with visited: 
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 X 0 X

Why: Fifth island is the last isolated land cell

Result:

Final count: 5 islands
Grid with all visited land marked as X:
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 X 0 X

Annotated Code

DSA Go

package main

import (
	"fmt"
)

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

	var dfs func(r, c int)
	dfs = func(r, c int) {
		if r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0' {
			return
		}
		grid[r][c] = '0' // mark visited
		// explore neighbors
		dfs(r-1, c) // up
		dfs(r+1, c) // down
		dfs(r, c-1) // left
		dfs(r, c+1) // right
	}

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == '1' {
				count++
				dfs(r, c) // mark all connected land
			}
		}
	}
	return count
}

func main() {
	grid := [][]byte{
		{'1','1','0','0','0'},
		{'1','1','0','0','1'},
		{'0','0','0','1','1'},
		{'0','0','0','0','0'},
		{'1','0','1','0','1'},
	}
	count := numIslands(grid)
	fmt.Printf("Number of islands: %d\n", count)
}

if grid[r][c] == '1' {

detect unvisited land cell to start island exploration

count++

increment island count for new island found

dfs(r, c)

explore and mark all connected land cells of this island

grid[r][c] = '0'

mark current cell as visited to avoid revisiting

dfs(r-1, c); dfs(r+1, c); dfs(r, c-1); dfs(r, c+1)

recursively visit all neighbors up, down, left, right

Output

Number of islands: 5

Complexity Analysis

Time: O(m*n) because each cell is visited at most once during DFS/BFS

Space: O(m*n) in worst case due to recursion stack or queue for BFS when all cells are land

vs Alternative: Compared to checking each cell and scanning neighbors repeatedly, DFS/BFS marks visited cells to avoid repeated work, making it efficient

Edge Cases

empty grid

returns 0 since no islands exist

DSA Go

if len(grid) == 0 { return 0 }

grid with all water

returns 0 since no land cells found

DSA Go

if grid[r][c] == '1' { ... }

grid with one big island

returns 1 after marking all connected land

DSA Go

dfs marks all connected land cells

When to Use This Pattern

When you see a grid with connected components and need to count groups, use DFS or BFS to explore neighbors and mark visited cells.

Common Mistakes

Mistake: Not marking visited cells, causing infinite loops or counting same island multiple times
Fix: Mark cells as visited by changing their value or using a separate visited structure

Mistake: Only checking horizontal neighbors and missing vertical connections
Fix: Check all four directions: up, down, left, right

Summary

Counts how many separate islands (connected groups of land) are in a grid.

Use when you need to find connected regions in a 2D grid.

The key is to explore all connected land cells from each unvisited land cell to mark one island.

Practice

1. What does the "Number of Islands" problem ask you to find in a grid of '1's and '0's?

easy

A. Count how many groups of connected '1's (islands) are in the grid

B. Find the largest island size

C. Count all '0's in the grid

D. Calculate the perimeter of islands

Solution

1. Step 1: Understand the grid content

   The grid contains '1's representing land and '0's representing water.

2. Step 2: Define the problem goal

   We need to count how many separate groups of connected '1's (islands) exist.

3. Final Answer:

   Count how many groups of connected '1's (islands) are in the grid -> Option A

4. Quick Check:

   Number of islands = count of connected '1' groups [OK]

Hint: Islands = connected '1's groups in grid [OK]

Common Mistakes:

• Counting individual '1's instead of groups
• Confusing '0's as islands
• Trying to find island size instead of count

2. Which of the following Go code snippets correctly starts a DFS from cell (i, j) in a grid to mark connected land?

easy

A. func dfs(grid [][]byte, i, j int) { if grid[i][j] == '1' { grid[i][j] = '1' } }

B. func dfs(grid [][]byte, i, j int) { for i < len(grid) { for j < len(grid[0]) { grid[i][j] = '0' } } }

C. func dfs(grid [][]byte, i, j int) { if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) || grid[i][j] == '0' { return } grid[i][j] = '0'; dfs(grid, i+1, j); dfs(grid, i-1, j); dfs(grid, i, j+1); dfs(grid, i, j-1) }

D. func dfs(grid [][]byte, i, j int) { if i > len(grid) || j > len(grid[0]) { return } grid[i][j] = '1' }

Solution

1. Step 1: Check boundary and water conditions

   func dfs(grid [][]byte, i, j int) { if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) || grid[i][j] == '0' { return } grid[i][j] = '0'; dfs(grid, i+1, j); dfs(grid, i-1, j); dfs(grid, i, j+1); dfs(grid, i, j-1) } correctly checks if indices are out of bounds or cell is water ('0'), then returns.

2. Step 2: Mark current land as visited and recurse

   func dfs(grid [][]byte, i, j int) { if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) || grid[i][j] == '0' { return } grid[i][j] = '0'; dfs(grid, i+1, j); dfs(grid, i-1, j); dfs(grid, i, j+1); dfs(grid, i, j-1) } marks current cell as '0' to avoid revisiting and calls dfs on neighbors up, down, left, right.

3. Final Answer:

   func dfs(grid [][]byte, i, j int) { if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) || grid[i][j] == '0' { return } grid[i][j] = '0'; dfs(grid, i+1, j); dfs(grid, i-1, j); dfs(grid, i, j+1); dfs(grid, i, j-1) } -> Option C

4. Quick Check:

   DFS marks visited land and explores neighbors [OK]

Hint: Check boundaries and mark visited before recursive calls [OK]

Common Mistakes:

• Not checking boundaries before access
• Not marking visited cells
• Using wrong loop instead of recursion

3. What is the output of the following Go code that counts islands using BFS on this grid?

grid := [][]byte{
  {'1','1','0','0','0'},
  {'1','1','0','0','0'},
  {'0','0','1','0','0'},
  {'0','0','0','1','1'},
}
count := numIslands(grid)
fmt.Println(count)

func numIslands(grid [][]byte) int {
  rows, cols := len(grid), len(grid[0])
  count := 0
  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' {
        count++
        queue := [][]int{{i,j}}
        grid[i][j] = '0'
        for len(queue) > 0 {
          r, c := queue[0][0], queue[0][1]
          queue = queue[1:]
          for _, d := range directions {
            nr, nc := r+d[0], c+d[1]
            if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1' {
              queue = append(queue, []int{nr,nc})
              grid[nr][nc] = '0'
            }
          }
        }
      }
    }
  }
  return count
}

medium

A. 1

B. 3

C. 4

D. 2

Solution

1. Step 1: Identify islands in the grid

   There are three groups of connected '1's: top-left block, middle single '1', bottom-right block.

2. Step 2: BFS marks visited and counts islands

   Each BFS call marks one island, so count increments 3 times.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Count islands = 3 [OK]

Hint: Count BFS runs triggered by unvisited '1's [OK]

Common Mistakes:

• Counting connected '1's individually
• Not marking visited cells
• Miscounting overlapping islands

4. The following DFS code for counting islands has a bug. What is the main issue?

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

medium

A. Boundary checks use '>' instead of '>=' causing out-of-range errors

B. It does not mark visited cells

C. It uses BFS instead of DFS

D. It does not check if grid[i][j] is '1'

Solution

1. Step 1: Analyze boundary conditions

   The code uses 'i > len(grid)' and 'j > len(grid[0])' which allows i or j to equal length, causing index out of range.

2. Step 2: Correct boundary check

   It should use 'i >= len(grid)' and 'j >= len(grid[0])' to prevent invalid access.

3. Final Answer:

   Boundary checks use '>' instead of '>=' causing out-of-range errors -> Option A

4. Quick Check:

   Use '>=' for boundary checks to avoid errors [OK]

Hint: Use '>=' for boundary checks in arrays [OK]

Common Mistakes:

• Using '>' instead of '>=' in boundary checks
• Forgetting to mark visited cells
• Mixing BFS and DFS logic

5. Given a grid where diagonal connections also count as connected land, how would you modify the BFS or DFS approach to count islands correctly?

hard

A. Count islands without marking visited cells

B. Only check horizontal neighbors, ignore vertical and diagonal

C. Use BFS only without any direction changes

D. Add diagonal directions (top-left, top-right, bottom-left, bottom-right) to the neighbors list

Solution

1. Step 1: Understand connection rules

   Diagonal connections mean neighbors include 8 directions, not just 4 (up, down, left, right).

2. Step 2: Modify neighbor directions

   Add diagonal directions: (-1,-1), (-1,1), (1,-1), (1,1) to the directions list used in BFS/DFS.

3. Final Answer:

   Add diagonal directions (top-left, top-right, bottom-left, bottom-right) to the neighbors list -> Option D

4. Quick Check:

   Include diagonals in neighbors for diagonal connectivity [OK]

Hint: Add diagonals to directions for 8-way connectivity [OK]

Common Mistakes:

• Ignoring diagonal neighbors
• Not updating directions list
• Counting without marking visited