Number of Islands BFS and DFS in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS-based Number of Islands

What is the output of the following Go code that counts islands using BFS?

DSA Go

package main

import "fmt"

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

    var bfs func(r, c int)
    bfs = func(r, c int) {
        queue := [][]int{{r, c}}
        grid[r][c] = '0'
        for len(queue) > 0 {
            curr := queue[0]
            queue = queue[1:]
            for _, d := range directions {
                nr, nc := curr[0]+d[0], curr[1]+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'
                }
            }
        }
    }

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

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

A 1

B 2

C 4

D 3

💡 Hint

Count how many separate groups of '1's are connected horizontally or vertically.

The BFS visits all connected land cells ('1') and marks them as water ('0'). The grid has three separate islands: top-left, middle, and bottom-right.

❓ Predict Output

intermediate

Output of DFS-based Number of Islands

What is the output of the following Go code that counts islands using DFS?

DSA Go

package main

import "fmt"

func numIslandsDFS(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    rows, cols := len(grid), 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'
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    }

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

func main() {
    grid := [][]byte{
        {'1','1','1','1','0'},
        {'1','1','0','1','0'},
        {'1','1','0','0','0'},
        {'0','0','0','0','0'},
    }
    fmt.Println(numIslandsDFS(grid))
}

A 2

B 1

C 3

D 0

💡 Hint

DFS marks all connected land cells as water recursively.

The grid has one big island connected horizontally and vertically.

🔧 Debug

advanced

Identify the error in BFS island counting code

What error will this Go code produce when counting islands using BFS?

DSA Go

package main

import "fmt"

func numIslands(grid [][]byte) int {
    rows, cols := len(grid), len(grid[0])
    count := 0
    directions := [][]int{{1,0},{-1,0},{0,1},{0,-1}}

    var bfs func(r, c int)
    bfs = func(r, c int) {
        queue := [][]int{{r, c}}
        grid[r][c] = '0'
        for len(queue) > 0 {
            curr := queue[0]
            queue = queue[1:]
            for _, d := range directions {
                nr, nc := curr[0]+d[0], curr[1]+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'
                }
            }
        }
    }

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

func main() {
    var grid [][]byte
    fmt.Println(numIslands(grid))
}

A runtime error: index out of range

B panic: nil pointer dereference

C 0

D 1

💡 Hint

Check how the code handles empty grid input.

The code does not check if grid is empty before accessing grid[0], causing index out of range error.

🧠 Conceptual

advanced

Why use BFS or DFS for Number of Islands?

Why do BFS and DFS work well for counting islands in a grid?

A They explore all connected land cells systematically, marking visited cells to avoid recounting.

B They sort the grid cells to group islands together.

C They convert the grid into a tree structure for easier counting.

D They use hashing to store island coordinates for quick lookup.

💡 Hint

Think about how connected components are found in graphs.

BFS and DFS traverse all connected cells of an island, marking them visited to count each island once.

🚀 Application

expert

Number of Islands with Diagonal Connections

Given the following grid, how many islands are counted if diagonal neighbors are also considered connected?

DSA Go

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

A 8

B 4

C 1

D 2

💡 Hint

Consider diagonal neighbors as connected when counting islands.

With diagonal connections (8-directional connectivity), all eight '1's form a single connected component in the checkerboard pattern.

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