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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS-based Number of Islands

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

DSA Python

from collections import deque

def num_islands_bfs(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = [[False]*cols for _ in range(rows)]
    def bfs(r, c):
        queue = deque()
        queue.append((r, c))
        visited[r][c] = True
        while queue:
            row, col = queue.popleft()
            for x, y in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]:
                if 0 <= x < rows and 0 <= y < cols and not visited[x][y] and grid[x][y] == '1':
                    visited[x][y] = True
                    queue.append((x, y))
    count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1' and not visited[i][j]:
                bfs(i, j)
                count += 1
    return count

grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
print(num_islands_bfs(grid))

A 3

B 2

C 4

D 1

💡 Hint

Count connected groups of '1's using BFS traversal.

The grid has three separate groups of connected '1's. BFS visits all connected cells in one group before moving to the next.

❓ Predict Output

intermediate

Output of DFS-based Number of Islands

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

DSA Python

def num_islands_dfs(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = [[False]*cols for _ in range(rows)]
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0' or visited[r][c]:
            return
        visited[r][c] = True
        dfs(r-1, c)
        dfs(r+1, c)
        dfs(r, c-1)
        dfs(r, c+1)
    count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1' and not visited[i][j]:
                dfs(i, j)
                count += 1
    return count

grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
print(num_islands_dfs(grid))

A 2

B 3

C 1

D 4

💡 Hint

Use DFS to mark all connected land cells.

DFS explores all connected land cells recursively. The grid has three distinct islands.

🧠 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 use hashing to store island coordinates efficiently.

B They sort the grid cells to find islands faster.

C They convert the grid into a tree structure automatically.

D They explore all connected land cells in one island before moving to another, ensuring each island is counted once.

💡 Hint

Think about how connected components are explored.

BFS and DFS traverse all connected land cells starting from one cell, marking them visited to avoid recounting, thus counting each island exactly once.

🔧 Debug

advanced

Identify the error in this DFS code for Number of Islands

What error will this code produce when run on a grid with islands? Code: def dfs(r, c): if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0': return visited[r][c] = True dfs(r-1, c) dfs(r+1, c) dfs(r, c-1) dfs(r, c+1) count = 0 for i in range(rows): for j in range(cols): if grid[i][j] == '1' and not visited[i][j]: dfs(i, j) count += 1

A IndexError due to out-of-range access

B RecursionError due to infinite recursion

C NameError because 'visited' is not defined

D No error, code runs correctly

💡 Hint

Check if all variables are declared before use.

The code uses 'visited' without defining or initializing it, causing a NameError.

🚀 Application

expert

Count islands with diagonal connections

Modify the standard Number of Islands problem to count islands where diagonally adjacent '1's are also connected. Which change to the BFS or DFS neighbor checks is correct?

A Add diagonal neighbors: (r-1,c-1), (r-1,c+1), (r+1,c-1), (r+1,c+1) to the neighbor list.

B Only check horizontal neighbors: (r,c-1), (r,c+1).

C Ignore vertical neighbors and only check diagonals.

D Use a queue instead of recursion to handle diagonals.

💡 Hint

Think about which neighbors define connectivity including diagonals.

Including diagonal neighbors in BFS or DFS ensures all connected land cells diagonally touching are counted as one island.

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