Number of Islands BFS and DFS in DSA Python

Mental Model

We find groups of connected land cells by exploring neighbors until no new land is found. Each group is one island.

Analogy: Imagine walking on a map of islands and water. When you step on land, you explore all connected land around you before moving on to find another island.

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

1 = land, 0 = water

Dry Run Walkthrough

Input: grid = [[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]]

Goal: Count how many separate islands (groups of connected 1s) are in the grid

Step 1: Start scanning from top-left; find first land at (0,0), start DFS to mark connected land

Visited cells marked:
X X 0 0 0
X X 0 0 1
0 0 0 1 1
0 0 0 0 0
1 0 1 0 1

Why: We found one island and mark all its land to avoid counting again

Step 2: Continue scanning; skip visited land; find next land at (1,4), start DFS to mark connected land

Visited cells marked:
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
1 0 1 0 1

Why: Second island found and fully marked

Step 3: Continue scanning; find land at (4,0), mark it as third island

Visited cells marked:
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 1 0 1

Why: Third island is a single cell

Step 4: Find land at (4,2), mark as fourth island

Visited cells marked:
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 X 0 1

Why: Fourth island is a single cell

Step 5: Find land at (4,4), mark as fifth island

Visited cells marked:
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 X 0 X

Why: Fifth island is a single cell

Result:

Final visited grid shows 5 islands marked:
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 X 0 X
Answer: 5 islands

Annotated Code

DSA Python

from collections import deque

class Solution:
    def numIslandsDFS(self, grid):
        if not grid or not grid[0]:
            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:
                return
            if grid[r][c] == '0' or visited[r][c]:
                return
            visited[r][c] = True
            dfs(r+1, c)  # down
            dfs(r-1, c)  # up
            dfs(r, c+1)  # right
            dfs(r, c-1)  # left
        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1' and not visited[r][c]:
                    dfs(r, c)  # explore island
                    count += 1
        return count

    def numIslandsBFS(self, grid):
        if not grid or not grid[0]:
            return 0
        rows, cols = len(grid), len(grid[0])
        visited = [[False]*cols for _ in range(rows)]
        count = 0
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1' and not visited[r][c]:
                    queue = deque()
                    queue.append((r,c))
                    visited[r][c] = True
                    while queue:
                        row, col = queue.popleft()
                        for dr, dc in directions:
                            nr, nc = row + dr, col + dc
                            if 0 <= nr < rows and 0 <= nc < cols:
                                if grid[nr][nc] == '1' and not visited[nr][nc]:
                                    queue.append((nr,nc))
                                    visited[nr][nc] = True
                    count += 1
        return count

# Driver code
input_grid = [
    ['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']
]
sol = Solution()
print("DFS number of islands:", sol.numIslandsDFS(input_grid))
print("BFS number of islands:", sol.numIslandsBFS(input_grid))

if grid[r][c] == '1' and not visited[r][c]:

start exploring new island when unvisited land found

dfs(r, c)

explore all connected land recursively to mark island

visited[r][c] = True

mark current cell as visited to avoid revisiting

queue.append((r,c))

start BFS queue with current land cell

while queue:

process all connected land cells in BFS order

for dr, dc in directions:

check all four neighbors for connected land

visited[nr][nc] = True

mark neighbor land cell visited when added to queue

count += 1

increment island count after fully exploring one island

Output

DFS number of islands: 5

BFS number of islands: 5

Complexity Analysis

Time: O(m*n) because each cell is visited once during DFS or BFS

Space: O(m*n) for the visited matrix and recursion/queue in worst case

vs Alternative: Naive approach checking each cell repeatedly is slower; BFS/DFS efficiently marks connected land once

Edge Cases

Empty grid

Returns 0 islands immediately

DSA Python

if not grid or not grid[0]: return 0

Grid with all water (all '0's)

No islands found, returns 0

DSA Python

if grid[r][c] == '1' and not visited[r][c]:

Grid with all land (all '1's)

Returns 1 island after marking all connected land

DSA Python

visited[r][c] = True inside DFS/BFS to mark all connected

When to Use This Pattern

When you see a grid with connected components and need to count groups, use BFS or DFS to explore neighbors and mark visited cells.

Common Mistakes

Mistake: Not marking visited cells, causing infinite loops or double counting
Fix: Always mark cells as visited when you add them to stack/queue or visit them

Mistake: Checking diagonal neighbors which is not required
Fix: Only check up, down, left, right neighbors

Summary

Counts how many separate islands of connected land exist in a grid using BFS or DFS.

Use when you need to find connected groups in a 2D grid.

The key is to explore all connected land from one cell before moving to the next unvisited land.

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