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

Concept Flow - Number of Islands BFS and DFS

Start: Grid with 0s and 1s

↓

Scan each cell

↓

Is cell '1' and not visited?

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') not visited is found, increase island count and use BFS or DFS to mark all connected land cells as visited, then continue scanning.

Execution Sample

DSA Python

def numIslands(grid):
    if not grid or not grid[0]:
        return 0
    count = 0
    visited = set()
    rows, cols = len(grid), len(grid[0])
    def bfs(r, c):
        q = [(r, c)]
        visited.add((r, c))
        while q:
            x, y = q.pop(0)
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1' and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    q.append((nx, ny))
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                bfs(r, c)
                count += 1
    return count

Counts islands by scanning grid and running BFS from each unvisited land cell, marking visited to avoid recounting.

Execution Table

Step	Operation	Current Cell (r,c)	Visited Cells	Island Count	Visual State
1	Start scanning grid	None	{}	0	[['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
2	Check cell	(0,0)	{(0,0)}	1	[['v','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
3	BFS neighbors	(0,1)	{(0,0),(0,1)}	1	[['v','v','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
4	BFS neighbors	(1,0)	{(0,0),(0,1),(1,0)}	1	[['v','v','0','0','0'], ['v','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
5	BFS neighbors	(1,1)	{(0,0),(0,1),(1,0),(1,1)}	1	[['v','v','0','0','0'], ['v','v','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
6	Continue scanning	(0,2)	{(0,0),(0,1),(1,0),(1,1)}	1	[['v','v','0','0','0'], ['v','v','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
7	Check cell	(2,2)	{(0,0),(0,1),(1,0),(1,1),(2,2)}	2	[['v','v','0','0','0'], ['v','v','0','0','0'], ['0','0','v','0','0'], ['0','0','0','1','1']]
8	Check cell	(3,3)	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3)}	3	[['v','v','0','0','0'], ['v','v','0','0','0'], ['0','0','v','0','0'], ['0','0','0','v','1']]
9	BFS neighbors	(3,4)	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3),(3,4)}	3	[['v','v','0','0','0'], ['v','v','0','0','0'], ['0','0','v','0','0'], ['0','0','0','v','v']]
10	End scanning	None	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3),(3,4)}	3	[['v','v','0','0','0'], ['v','v','0','0','0'], ['0','0','v','0','0'], ['0','0','0','v','v']]

💡 All cells scanned; all connected land cells marked visited; total islands counted as 3

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 9	Final
count	0	1	1	2	3	3
visited	{}	{(0,0)}	{(0,0),(0,1),(1,0),(1,1)}	{(0,0),(0,1),(1,0),(1,1),(2,2)}	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3),(3,4)}	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3),(3,4)}

Key Moments - 3 Insights

Why do we mark cells as visited during BFS/DFS?

Marking cells as visited prevents counting the same land cell multiple times as shown in steps 2 to 5 where connected cells are marked to avoid recounting.

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

Because each unvisited '1' represents a new island start, as seen in steps 2, 7, and 8 where count increments only when a new land cell not visited before is found.

Why do we continue scanning after BFS/DFS finishes?

To find other islands in the grid, since BFS/DFS only marks connected land cells of one island, the rest must be checked as in steps 6 and 8.

Visual Quiz - 3 Questions

Look at the execution table, what is the island count after step 5?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Island Count' column at step 5 in the execution_table.

At which step does the BFS mark the cell (3,4) as visited?

A Step 7

B Step 9

C Step 8

D Step 10

💡 Hint

Look at the 'Current Cell' and 'Visited Cells' columns in the execution_table rows.

If the grid had no '1's, what would be the final island count?

A 1

B Number of rows

C 0

D Number of columns

💡 Hint

Refer to the variable_tracker for 'count' starting at 0 and only increasing when '1' is found.

Concept Snapshot

Number of Islands (BFS/DFS):
- Scan each cell in grid
- If cell is '1' and not visited:
  - Increment island count
  - Use BFS/DFS to mark connected '1's visited
- Continue until all cells checked
- Return total island count

Full Transcript

The Number of Islands problem involves scanning a grid of '1's and '0's to count how many separate islands exist. We scan each cell; when we find a '1' that is not visited, we increase the island count and run BFS or DFS to mark all connected land cells as visited. This prevents counting the same island multiple times. We continue scanning until all cells are processed. The final count is the number of islands. The execution table shows step-by-step how cells are visited and islands counted. The variable tracker shows how the count and visited set change. Key moments clarify why we mark visited cells and why we increment count only on new land cells. The visual quiz tests understanding of these steps.

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 all '0's in the grid

B. Find the largest island size

C. Count how many groups of connected '1's (islands) exist

D. Calculate the perimeter of all islands

Solution

1. Step 1: Understand the grid representation

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

2. Step 2: Identify what the problem asks

   It asks to count how many separate groups of connected '1's (islands) are present.

3. Final Answer:

   Count how many groups of connected '1's (islands) exist -> Option C

4. Quick Check:

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

Hint: Islands = groups of connected '1's, count them [OK]

Common Mistakes:

• Confusing island count with island size
• Counting '0's instead of '1's
• Calculating perimeter instead of count

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

easy

A. def dfs(i, j): if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or 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)

B. def dfs(i, j): while grid[i][j] == '1': grid[i][j] = '0'; dfs(i+1,j); dfs(i-1,j)

C. def dfs(i, j): if grid[i][j] == '1': return; dfs(i+1,j); dfs(i-1,j)

D. def dfs(i, j): for x in range(len(grid)): for y in range(len(grid[0])): dfs(x,y)

Solution

1. Step 1: Check boundary and water conditions

   def dfs(i, j): if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or 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) correctly checks if indices are out of bounds or cell is water ('0') and returns.

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

   def dfs(i, j): if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or 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) marks grid[i][j] = '0' to avoid revisiting and calls dfs on all four neighbors.

3. Final Answer:

   Option A code correctly implements DFS with boundary checks and marking visited -> Option A

4. Quick Check:

   DFS with boundary and visited marking = def dfs(i, j): if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or 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) [OK]

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

Common Mistakes:

• Not checking boundaries before recursion
• Not marking visited cells
• Using loops incorrectly inside DFS

3. What is the output of the following code snippet for the given grid?

grid = [
  ['1','1','0','0'],
  ['1','0','0','1'],
  ['0','0','1','1'],
  ['0','0','0','0']
]

count = 0
for i in range(len(grid)):
    for j in range(len(grid[0])):
        if grid[i][j] == '1':
            count += 1
            stack = [(i,j)]
            while stack:
                x,y = stack.pop()
                if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == '1':
                    grid[x][y] = '0'
                    stack.extend([(x+1,y),(x-1,y),(x,y+1),(x,y-1)])
print(count)

medium

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Identify islands in the grid

   The grid has three islands: top-left (cells (0,0),(0,1),(1,0)), single cell island at (1,3), and bottom-right island (cells (2,2),(2,3)).

2. Step 2: Trace the DFS using stack

   Each '1' found triggers DFS marking connected '1's as '0'. The count increments for each new island found. Total islands counted = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Number of islands found by DFS = 3 [OK]

Hint: Count connected '1' groups using DFS stack traversal [OK]

Common Mistakes:

• Counting each '1' without marking visited
• Misidentifying connected cells
• Off-by-one errors in loops

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

def dfs(i, j):
    if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
        return
    if grid[i][j] == '0':
        return
    dfs(i+1, j)
    dfs(i-1, j)
    dfs(i, j+1)
    dfs(i, j-1)

count = 0
for i in range(len(grid)):
    for j in range(len(grid[0])):
        if grid[i][j] == '1':
            count += 1
            dfs(i, j)
print(count)

medium

A. The DFS only checks horizontal neighbors

B. The boundary checks are incorrect

C. The count variable is not incremented properly

D. The code does not mark visited cells, causing infinite recursion

Solution

1. Step 1: Analyze DFS function behavior

   The DFS checks boundaries and water but never marks visited land cells as '0' or visited.

2. Step 2: Identify consequence of missing visited marking

   Without marking visited, DFS revisits same cells repeatedly, causing infinite recursion or stack overflow.

3. Final Answer:

   The code does not mark visited cells, causing infinite recursion -> Option D

4. Quick Check:

   Missing visited marking causes infinite recursion [OK]

Hint: Always mark visited cells to avoid infinite loops in DFS [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Incorrect boundary conditions
• Incrementing count inside DFS

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. Add diagonal neighbors (i+1,j+1), (i+1,j-1), (i-1,j+1), (i-1,j-1) to the search directions

B. Only count horizontal neighbors and ignore vertical and diagonal

C. Use BFS but skip marking visited cells

D. Count islands by summing all '1's without traversal

Solution

1. Step 1: Understand diagonal connectivity

   Diagonal connections mean neighbors include cells diagonally adjacent, not just up/down/left/right.

2. Step 2: Modify search directions

   Add diagonal neighbors (i+1,j+1), (i+1,j-1), (i-1,j+1), (i-1,j-1) to BFS or DFS neighbor checks to include diagonals.

3. Final Answer:

   Add diagonal neighbors (i+1,j+1), (i+1,j-1), (i-1,j+1), (i-1,j-1) to the search directions -> Option A

4. Quick Check:

   Include diagonals in neighbors for diagonal connectivity [OK]

Hint: Include diagonal neighbors in BFS/DFS directions [OK]

Common Mistakes:

• Ignoring diagonal neighbors
• Not marking visited cells
• Counting without traversal