Number of Islands BFS and DFS in DSA Go - Deep Dive

Overview - Number of Islands BFS and DFS

What is it?

Number of Islands is a problem where you count how many separate groups of connected 'land' cells exist in a grid. Each cell can be either land or water. We use BFS (Breadth-First Search) or DFS (Depth-First Search) to explore and mark connected land cells as one island.

Why it matters

This problem helps us understand how to explore connected parts in a grid, which is common in maps, games, and network analysis. Without this, we couldn't easily find or count connected regions, making tasks like flood fill, cluster detection, or pathfinding much harder.

Where it fits

Before this, you should know basic arrays and loops. After this, you can learn graph traversal algorithms more deeply, like shortest path or cycle detection, and apply these ideas to complex grid or graph problems.

Mental Model

Core Idea

Explore each land cell and mark all connected land cells as one island using BFS or DFS to avoid counting them multiple times.

Think of it like...

Imagine a map with patches of forest (land) and lakes (water). To count how many forests there are, you start at one tree and walk through all connected trees until you reach water or the edge, then move to the next unvisited tree to find another forest.

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

Islands found:
  Island 1: top-left cluster (cells with '1' connected)
  Island 2: middle-right cluster
  Island 3: bottom-left single cell
  Island 4: bottom-middle single cell
  Island 5: bottom-right single cell

Build-Up - 7 Steps

1

Foundation

Understanding the grid and islands

Concept: Introduce the grid layout and what counts as land or water.

We have a 2D grid where each cell is either '1' (land) or '0' (water). Islands are groups of '1's connected horizontally or vertically (not diagonally). Our goal is to count how many such groups exist.

Result

You can visually identify separate islands by looking at connected '1's.

Understanding the problem setup is key to knowing what to search for and how to group connected cells.

2

Foundation

Basic DFS to explore connected land

Concept: Use Depth-First Search to visit all connected land cells starting from one cell.

Pick a land cell, mark it visited, then recursively visit its neighbors (up, down, left, right) if they are land and unvisited. This explores one island fully.

Result

After DFS, all cells of one island are marked visited, so they won't be counted again.

DFS helps us explore all connected parts of an island in a simple, recursive way.

3

Intermediate

Counting islands with DFS

🤔Before reading on: Do you think counting islands means running DFS once or multiple times? Commit to your answer.

Concept: Run DFS from every unvisited land cell and count how many times you start DFS.

Loop through each cell in the grid. When you find an unvisited land cell, run DFS to mark its island, then increase the island count by one. Continue until all cells are checked.

Result

The count equals the number of islands in the grid.

Counting islands is about counting how many times you find a new unvisited land cell and explore its connected group.

4

Intermediate

Using BFS instead of DFS

🤔Before reading on: Will BFS and DFS give different island counts? Commit to your answer.

Concept: Breadth-First Search can also explore connected land cells by visiting neighbors level by level.

Instead of recursion, use a queue to visit neighbors. Start from a land cell, add it to the queue, then repeatedly visit and enqueue its unvisited land neighbors until done. This marks one island.

Result

BFS also marks all connected land cells of one island, giving the same count as DFS.

BFS and DFS are interchangeable for this problem; choice depends on preference or constraints.

5

Intermediate

Marking visited cells to avoid repeats

Concept: Keep track of visited cells to prevent counting the same island multiple times.

Use a separate 2D boolean array or modify the grid to mark cells as visited after exploring them. This ensures each land cell is processed once.

Result

No island is counted more than once, and the algorithm finishes efficiently.

Tracking visited cells is essential to avoid infinite loops and double counting.

6

Advanced

Optimizing space by modifying the grid

🤔Before reading on: Is it safe to change the input grid to mark visited cells? Commit to your answer.

Concept: Instead of extra memory, mark visited land cells by changing '1' to '0' in the grid itself.

When visiting a land cell, set its value to '0' to mark it visited. This saves space but changes input data.

Result

Algorithm uses less memory but input grid is altered.

Modifying input can optimize space but may not be allowed if original data must be preserved.

7

Expert

Handling large grids and stack overflow

🤔Before reading on: Will recursive DFS always work on very large grids? Commit to your answer.

Concept: Recursive DFS can cause stack overflow on large grids; iterative DFS or BFS is safer.

Use an explicit stack for DFS or a queue for BFS to avoid deep recursion. This prevents crashes in production environments.

Result

Algorithm runs reliably on large inputs without crashing.

Knowing recursion limits and switching to iterative methods is crucial for robust, scalable solutions.

Under the Hood

The algorithm treats the grid as a graph where each land cell is a node connected to its adjacent land nodes. BFS or DFS traverses this graph to find connected components (islands). Visited nodes are marked to prevent revisiting. The traversal explores neighbors systematically until the entire island is covered.

Why designed this way?

Grid problems map naturally to graph traversal. BFS and DFS are classic, simple, and efficient ways to explore connected nodes. Marking visited nodes avoids infinite loops and double counting. Alternatives like union-find exist but are more complex for beginners.

Grid as graph:
  [1]--[1]   [0]   [0]   [0]
   |     
  [1]   [1]   [0]   [0]   [1]

Traversal flow:
  Start at [1], visit neighbors -> mark visited
  Continue until no new neighbors
  Move to next unvisited land cell

Visited marks prevent re-exploration.

Myth Busters - 4 Common Misconceptions

Quick: Does diagonal adjacency count as connected land? Commit to yes or no.

Common Belief: Many think diagonal neighbors count as connected land cells.

Reality: Only horizontal and vertical neighbors count as connected; diagonals do not.

Why it matters: Counting diagonals would merge separate islands incorrectly, giving wrong island counts.

Quick: Will BFS and DFS give different island counts? Commit to yes or no.

Common Belief: Some believe BFS and DFS produce different results for island counting.

Reality: Both BFS and DFS find the same connected components and thus the same island count.

Why it matters: Choosing one over the other won't affect correctness, only performance or style.

Quick: Can you count islands without marking visited cells? Commit to yes or no.

Common Belief: Some think you can count islands by just scanning the grid once without marking visited cells.

Reality: Without marking visited cells, you will count the same island multiple times, inflating the count.

Why it matters: Failing to mark visited cells leads to incorrect results and inefficient repeated work.

Quick: Does modifying the input grid always cause problems? Commit to yes or no.

Common Belief: Many think changing the input grid to mark visited cells is always bad.

Reality: Modifying the input is safe if you don't need the original data later and saves memory.

Why it matters: Knowing when it's safe to modify input helps optimize space without unnecessary copying.

Expert Zone

1

Using iterative DFS with an explicit stack avoids recursion limits and improves control over traversal order.

2

Choosing BFS can be better when shortest path or level order information is needed alongside island counting.

3

Union-Find data structure can solve this problem efficiently in dynamic scenarios where the grid changes over time.

When NOT to use

Avoid BFS/DFS if the grid is extremely large and memory is limited; consider Union-Find or specialized streaming algorithms instead.

Production Patterns

In real systems, island counting is used in image processing for connected component labeling, network cluster detection, and game map analysis, often combined with other graph algorithms for richer insights.

Connections

Connected Components in Graphs

Number of Islands is a special case of finding connected components in an undirected graph.

Understanding islands as connected components helps apply graph theory tools and algorithms broadly.

Flood Fill Algorithm

Flood fill uses similar BFS/DFS traversal to fill connected areas, like painting a region in an image.

Knowing island counting clarifies how flood fill works and vice versa, as both explore connected regions.

Epidemiology Spread Models

Modeling disease spread on a grid uses similar neighbor-based traversal to track infection clusters.

Recognizing traversal patterns in island counting helps understand how infections spread spatially in populations.

Common Pitfalls

#1 Counting islands without marking visited cells causes double counting.

Wrong approach:

for i := range grid {
for j := range grid[0] {
if grid[i][j] == '1' {
count++
}
}
}

Correct approach:

for i := range grid {
for j := range grid[0] {
if grid[i][j] == '1' {
dfs(i, j)
count++
}
}
}

func dfs(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(i+1, j)
dfs(i-1, j)
dfs(i, j+1)
dfs(i, j-1)
}

Root cause:

Not marking visited cells means the same island cells are counted multiple times.

#2 Using recursive DFS on very large grids causes stack overflow.

Wrong approach:

func dfs(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(i+1, j)
dfs(i-1, j)
dfs(i, j+1)
dfs(i, j-1)
}

Correct approach:

func dfsIterative(i, j int) {
stack := [][]int{{i, j}}
for len(stack) > 0 {
cell := stack[len(stack)-1]
stack = stack[:len(stack)-1]
x, y := cell[0], cell[1]
if x < 0 || y < 0 || x >= len(grid) || y >= len(grid[0]) || grid[x][y] == '0' {
continue
}
grid[x][y] = '0'
stack = append(stack, []int{x + 1, y}, []int{x - 1, y}, []int{x, y + 1}, []int{x, y - 1})
}
}

Root cause:

Recursive calls can exceed the call stack limit on large inputs.

#3 Counting diagonal neighbors as connected land.

Wrong approach:

func dfs(i, j int) {
// also visit diagonals
dfs(i+1, j+1)
dfs(i+1, j-1)
dfs(i-1, j+1)
dfs(i-1, j-1)
}

Correct approach:

func dfs(i, j int) {
dfs(i+1, j)
dfs(i-1, j)
dfs(i, j+1)
dfs(i, j-1)
}

Root cause:

Misunderstanding adjacency rules leads to incorrect island grouping.

Key Takeaways

Number of Islands counts connected groups of land cells in a grid using BFS or DFS traversal.

Marking visited cells is essential to avoid counting the same island multiple times.

BFS and DFS both work and produce the same result; choice depends on context and constraints.

Modifying the input grid can save memory but may not always be allowed.

Iterative traversal methods prevent stack overflow on large grids, making solutions more robust.

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