Number of Islands BFS and DFS in DSA Python - 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 this map. An island is a group of connected land cells (horizontally or vertically). This is useful in games, geography apps, or flood simulations.

🎯 Goal: You will build a program that counts the number of islands in a grid using two methods: Breadth-First Search (BFS) and Depth-First Search (DFS). You will first set up the grid, then configure helper variables, implement BFS and DFS to explore islands, and finally print the count of islands found.

📋 What You'll Learn

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

Create a variable rows for the number of rows and cols for the number of columns in grid

Write a function bfs that uses a queue to explore connected land cells starting from a given cell

Write a function dfs that uses recursion to explore connected land cells starting from a given cell

Count islands by checking each cell and using BFS or DFS to mark visited land cells

Print the number of islands found using BFS and DFS

💡 Why This Matters

🌍 Real World

Counting islands helps in analyzing maps, satellite images, and game worlds to understand land distribution and connectivity.

💼 Career

This problem teaches graph traversal techniques useful in software engineering roles involving grids, maps, image processing, and network connectivity.

1

Create the map grid

Create a 2D list called grid with these exact rows and columns:
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']

DSA Python

# Create the grid variable with the exact rows
# Your code here

Hint

Think of grid as a list of lists, where each inner list is a row of the map.

2

Set up row and column counts

Create variables rows and cols to store the number of rows and columns in grid respectively.

DSA Python

grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
]
# Create rows and cols variables
# Your code here

Hint

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

3

Write BFS and DFS functions to explore islands

Write two functions:
1. bfs(r, c) that uses a queue to visit all connected land cells starting from row r and column c.
2. dfs(r, c) that uses recursion to visit all connected land cells starting from row r and column c.
Both functions should mark visited cells by changing '1' to '0' in grid.

DSA Python

grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
]
rows = len(grid)
cols = len(grid[0])

# Write bfs(r, c) function using a queue
# Write dfs(r, c) function using recursion
# Your code here

Hint

Use a queue for BFS and recursion for DFS. Mark visited land by changing '1' to '0'.

4

Count islands and print results

Use the bfs function to count islands in a copy of grid called grid_bfs. Then use the dfs function to count islands in another copy called grid_dfs. Print the counts as:
print("Number of islands (BFS):", count_bfs)
print("Number of islands (DFS):", count_dfs)

DSA Python

from collections import deque

grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
]
rows = len(grid)
cols = len(grid[0])

def bfs(r, c):
    queue = deque()
    queue.append((r, c))
    grid[r][c] = '0'
    while queue:
        row, col = queue.popleft()
        for x, y in [(row-1, col), (row+1, col), (row, col-1), (row, col+1)]:
            if 0 = rows or c = cols or 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)

# Count islands using bfs and dfs on copies of grid
# Print the counts
# Your code here

Hint

Make copies of grid to keep BFS and DFS separate. Count islands by calling BFS or DFS on each unvisited land cell.

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