Number of Islands BFS and DFS in DSA Go - Build from Scratch

Number of Islands BFS and DFS

📖 Scenario: Imagine you have a map represented as a grid of water and land cells. You want to find out how many separate islands are on the map. An island is a group of connected land cells (horizontally or vertically). This is useful in games, geography apps, or robotics navigation.

🎯 Goal: Build a Go program that counts the number of islands in a grid using both BFS (Breadth-First Search) and DFS (Depth-First Search) methods.

📋 What You'll Learn

Create a 2D slice of bytes called grid with exact values representing land ('1') and water ('0')

Create a variable rows and cols to store grid dimensions

Implement a BFS function bfs to mark connected land cells as visited

Implement a DFS function dfs to mark connected land cells as visited

Write a main function to count islands using BFS and DFS separately

Print the number of islands found by BFS and DFS

💡 Why This Matters

🌍 Real World

Counting islands helps in image processing, robotics pathfinding, and geographical mapping where connected regions need identification.

💼 Career

Understanding BFS and DFS is essential for software engineers working on graph problems, game development, and spatial data analysis.

1

Create the grid data

Create a 2D slice of bytes called grid with these exact rows: {'1','1','0','0','0'}, {'1','1','0','0','0'}, {'0','0','1','0','0'}, {'0','0','0','1','1'}.

DSA Go

// Create the grid variable with the exact values
// Your code here

Hint

Use a 2D slice of bytes with the exact rows and columns as shown.

2

Add grid dimensions variables

Create two variables: rows to store the number of rows in grid, and cols to store the number of columns in grid.

DSA Go

package main

var grid = [][]byte{
	{'1','1','0','0','0'},
	{'1','1','0','0','0'},
	{'0','0','1','0','0'},
	{'0','0','0','1','1'},
}

func main() {
	// Create rows and cols variables
	// Your code here
}

Hint

Use len(grid) for rows and len(grid[0]) for cols.

3

Implement BFS and DFS functions

Implement two functions: bfs and dfs. Both take grid, row, col, rows, and cols as parameters. They mark connected land cells ('1') as visited by changing them to '0'. Use BFS with a queue in bfs and recursion in dfs.

DSA Go

package main

import "container/list"

var grid = [][]byte{
	{'1','1','0','0','0'},
	{'1','1','0','0','0'},
	{'0','0','1','0','0'},
	{'0','0','0','1','1'},
}

func bfs(grid [][]byte, row, col, rows, cols int) {
	// Your code here
}

func dfs(grid [][]byte, row, col, rows, cols int) {
	// Your code here
}

func main() {
	rows := len(grid)
	cols := len(grid[0])

	// Step 2 complete
}

Hint

Use a queue from container/list for BFS and recursion for DFS. Mark visited cells by setting them to '0'.

4

Count islands and print results

In main, create two copies of grid called gridBFS and gridDFS. Count islands using BFS on gridBFS and DFS on gridDFS. Print the counts with fmt.Println as "Number of islands (BFS): X" and "Number of islands (DFS): Y".

DSA Go

package main

import (
	"container/list"
	"fmt"
)

var grid = [][]byte{
	{'1','1','0','0','0'},
	{'1','1','0','0','0'},
	{'0','0','1','0','0'},
	{'0','0','0','1','1'},
}

func bfs(grid [][]byte, row, col, rows, cols int) {
	queue := list.New()
	queue.PushBack([2]int{row, col})
	grid[row][col] = '0'

	dirs := [][2]int{{-1,0},{1,0},{0,-1},{0,1}}

	for queue.Len() > 0 {
		front := queue.Remove(queue.Front()).([2]int)
		r, c := front[0], front[1]

		for _, d := range dirs {
			nr, nc := r+d[0], c+d[1]
			if nr >= 0 && nr = 0 && nc = rows || col = cols || grid[row][col] == '0' {
		return
	}
	grid[row][col] = '0'

	dirs := [][2]int{{-1,0},{1,0},{0,-1},{0,1}}
	for _, d := range dirs {
		dfs(grid, row+d[0], col+d[1], rows, cols)
	}
}

func main() {
	rows := len(grid)
	cols := len(grid[0])

	// Create copies of grid
	// Count islands using bfs on gridBFS
	// Count islands using dfs on gridDFS
	// Print results
	// Your code here
}

Hint

Make copies of the grid to avoid modifying the original. Count islands by calling bfs or dfs on each unvisited land cell. Print the counts.

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