Number of Islands BFS and DFS in DSA Go - Execution Trace

Concept Flow - Number of Islands BFS and DFS

Start: Grid with 0s and 1s

↓

Scan each cell

↓

Is cell '1' and unvisited?

No→Move to next cell

Yes↓

Increment island count

↓

Run BFS or DFS to mark connected '1's as visited

↓

Mark all connected land cells

↓

Continue scanning grid

↓

End: Return total island count

Scan the grid cell by cell; when a land cell ('1') is found and unvisited, start BFS or DFS to mark all connected land cells as visited, then continue scanning until all cells are processed.

Execution Sample

DSA Go

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

Counts islands by scanning grid and using DFS to mark connected lands.

Execution Table

Step	Operation	Current Cell	Action	Grid State (Visual)	Island Count
1	Scan cell	(0,0)	Cell is '1', start DFS	1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0	1
2	DFS mark	(0,0)	Mark visited (set to '0')	0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0	1
3	DFS mark	(0,1)	Mark visited (set to '0')	0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0	1
4	DFS mark	(1,0)	Mark visited (set to '0')	0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0	1
5	Scan cell	(0,1)	Already visited (0), skip	0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0	1
6	Scan cell	(0,2)	Water (0), skip	0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0	1
7	Scan cell	(0,3)	Water (0), skip	0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0	1
8	Scan cell	(1,3)	Cell is '1', start DFS	0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0	2
9	DFS mark	(1,3)	Mark visited (set to '0')	0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0	2
10	DFS mark	(2,3)	Mark visited (set to '0')	0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0	2
11	DFS mark	(2,2)	Mark visited (set to '0')	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	2
12	Scan cell	(2,2)	Already visited (0), skip	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	2
13	Scan cell	(3,3)	Water (0), skip	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	2
14	End	-	All cells scanned	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	2

💡 All cells scanned, no unvisited land cells remain

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 10	Final
count	0	1	1	2	2
grid	Original grid	Marked (0,0),(0,1),(1,0)	Marked first island fully	Marked second island fully	All visited marked as '0'

Key Moments - 3 Insights

Why do we mark visited land cells as '0' during DFS?

Marking visited cells as '0' prevents revisiting the same land, as shown in steps 2-4 and 9-11 in the execution_table.

Why do we increase the island count only when we find an unvisited '1'?

Because each unvisited '1' represents a new island start, as seen in steps 1 and 8 where count increments before DFS.

Why does DFS visit neighbors only in four directions?

Because islands are connected horizontally or vertically, not diagonally, so DFS checks up, down, left, right neighbors during marking.

Visual Quiz - 3 Questions

Look at the execution_table at Step 8, what is the island count after scanning cell (1,3)?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Island Count' column at Step 8 in the execution_table.

At which step does the DFS finish marking the first island?

A Step 4

B Step 3

C Step 5

D Step 6

💡 Hint

Look at the grid state changes and pointer changes in steps 2-5 in the execution_table.

If we do not mark visited cells as '0', what will happen to the island count?

A It will be correct

B It will be less than actual

C It will be more than actual

D It will be zero

💡 Hint

Refer to key_moments about marking visited cells and how revisiting affects counting.

Concept Snapshot

Number of Islands counts connected groups of '1's in a grid.
Scan each cell; if '1' and unvisited, increment count and run DFS/BFS.
DFS/BFS marks all connected lands as visited (e.g., set to '0').
Only horizontal and vertical neighbors count as connected.
Return total count after scanning all cells.

Full Transcript

This visualization shows how to count islands in a grid using DFS or BFS. We scan each cell. When we find a land cell '1' that is not visited, we increase the island count. Then we run DFS or BFS to mark all connected land cells as visited by changing them to '0'. This prevents counting the same island multiple times. We only consider neighbors up, down, left, and right as connected. The process continues until all cells are scanned. The final count is the number of islands.

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