Number of Islands BFS and DFS in DSA Python - Deep Dive

Overview - Number of Islands BFS and DFS

What is it?

Number of Islands is a problem where you count how many separate groups of connected 'land' cells exist in a grid. Each cell can be either land or water. We use BFS (Breadth-First Search) or DFS (Depth-First Search) to explore and mark connected land cells as one island.

Why it matters

This problem helps us understand how to explore connected areas in grids, which is useful in maps, image processing, and network analysis. Without this, we couldn't easily find clusters or groups in data arranged in grids, making many real-world tasks harder.

Where it fits

Before this, you should know basic arrays and loops. After this, you can learn graph traversal algorithms more deeply and solve related problems like shortest path or connected components.

Mental Model

Core Idea

Counting islands means exploring each land cell and marking all connected land cells as one group using BFS or DFS.

Think of it like...

Imagine a map with lakes and islands. You walk on land and mark every connected piece you can reach without stepping into water. Each separate walk you start counts as a new 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

Islands found:
  Island 1: top-left cluster of 1s
  Island 2: middle-right cluster
  Island 3: bottom-left single 1
  Island 4: bottom-middle single 1
  Island 5: bottom-right single 1

Build-Up - 7 Steps

1

Foundation

Understanding the grid and islands

Concept: Learn what the grid looks like and what counts as an island.

A grid is a 2D list where each cell is '1' (land) or '0' (water). An island is a group of '1's connected horizontally or vertically (not diagonally). We want to count how many such groups exist.

Result

You can identify separate groups of connected '1's visually.

Knowing the problem setup clearly helps you understand what to search for and how to group connected cells.

2

Foundation

Basic DFS traversal on grid

Concept: Use DFS to explore all connected land cells starting from one cell.

Starting from a land cell, recursively visit its neighbors (up, down, left, right) if they are land and not visited. Mark visited cells to avoid counting them again.

Result

All connected land cells from the start cell are marked visited.

DFS lets you explore one island fully before moving to the next, ensuring no double counting.

3

Intermediate

Counting islands using DFS

🤔Before reading on: Do you think counting islands means counting every land cell or counting connected groups? Commit to your answer.

Concept: Combine DFS with a loop over the grid to count how many times you start a DFS on unvisited land cells.

Loop over each cell. If it's land and not visited, start DFS to mark the whole island. Increase island count by one. Continue until all cells are checked.

Result

You get the total number of islands in the grid.

Understanding that each DFS start represents a new island is key to counting correctly.

4

Intermediate

Using BFS instead of DFS

🤔Before reading on: Do you think BFS and DFS will find different numbers of islands? Commit to your answer.

Concept: Use BFS with a queue to explore connected land cells level by level instead of recursion.

When you find an unvisited land cell, add it to a queue. While queue not empty, pop cell, mark neighbors if land and unvisited, add them to queue. Mark all connected cells visited.

Result

BFS also marks all cells of one island, allowing counting islands similarly to DFS.

Knowing BFS and DFS are interchangeable here helps choose based on language or stack limits.

5

Intermediate

Handling edge cases and grid boundaries

🤔Before reading on: What happens if you forget to check grid boundaries during traversal? Commit to your answer.

Concept: Ensure traversal does not go outside grid limits to avoid errors.

Before visiting neighbors, check if row and column indices are within grid size. Skip if out of bounds.

Result

Traversal runs safely without errors or crashes.

Boundary checks prevent runtime errors and ensure correct exploration.

6

Advanced

Optimizing space by modifying grid in-place

🤔Before reading on: Is it better to use extra memory for visited or modify the grid directly? Commit to your answer.

Concept: Instead of using a separate visited array, mark visited land cells by changing their value in the grid.

When visiting a land cell, change its value from '1' to '0' to mark visited. This saves extra memory.

Result

Memory usage is reduced, but original grid is changed.

Knowing this tradeoff helps optimize memory in constrained environments.

7

Expert

Surprising behavior with diagonal connections

🤔Before reading on: Does counting islands include diagonal neighbors by default? Commit to your answer.

Concept: Standard problem counts only horizontal and vertical neighbors. Including diagonals changes island count.

If you add diagonal neighbors to traversal, some islands merge, reducing total count. This changes problem meaning.

Result

Different neighbor rules lead to different island counts.

Understanding neighbor definitions is crucial to correctly solving and interpreting results.

Under the Hood

The grid is treated like a graph where each cell is a node connected to up to four neighbors. DFS uses recursion or a stack to explore nodes deeply, while BFS uses a queue to explore nodes level by level. Visited nodes are tracked to avoid revisiting and infinite loops.

Why designed this way?

DFS and BFS are classic graph traversal algorithms chosen because grids naturally form graphs with simple neighbor relations. They efficiently explore connected components without extra complex data structures.

Grid cell connections:

  [r,c]
   │  │
 [r-1,c] [r,c-1] [r,c+1] [r+1,c]

Traversal flow:

Start -> Visit neighbors -> Mark visited -> Repeat until no new neighbors

Myth Busters - 4 Common Misconceptions

Quick: Does counting islands mean counting every land cell separately? Commit yes or no.

Common Belief: Counting islands means counting every '1' cell individually.

Reality: Islands are groups of connected '1's counted as one, not each cell separately.

Why it matters: Counting each cell separately inflates the number and misses the concept of connected land.

Quick: Will BFS and DFS give different island counts? Commit yes or no.

Common Belief: BFS and DFS produce different results for number of islands.

Reality: Both BFS and DFS find the same connected components and thus the same island count.

Why it matters: Believing they differ can cause confusion and wrong algorithm choice.

Quick: Does including diagonal neighbors count as standard in this problem? Commit yes or no.

Common Belief: Diagonal neighbors are always included when counting islands.

Reality: Standard problem counts only horizontal and vertical neighbors; diagonals change the count.

Why it matters: Misunderstanding neighbor rules leads to inconsistent results and wrong answers.

Quick: Can you safely skip boundary checks during traversal? Commit yes or no.

Common Belief: Boundary checks are optional and can be skipped for simplicity.

Reality: Skipping boundary checks causes errors or crashes when accessing invalid grid positions.

Why it matters: Ignoring boundaries leads to runtime errors and program failure.

Expert Zone

1

Changing the grid in-place to mark visited saves memory but destroys original data, which may be needed later.

2

Recursive DFS can cause stack overflow on large grids; iterative DFS or BFS avoids this.

3

The choice between BFS and DFS can affect performance depending on grid shape and size.

When NOT to use

This approach is not suitable for grids with weighted edges or when shortest path distances are needed; use algorithms like Dijkstra instead.

Production Patterns

Used in image segmentation to find connected regions, in game maps to detect zones, and in network analysis to find connected clusters.

Connections

Graph Connected Components

Number of Islands is a special case of finding connected components in a graph.

Understanding connected components in graphs generalizes the island counting problem to many data structures.

Flood Fill Algorithm

Number of Islands uses similar traversal to flood fill which colors connected areas.

Knowing flood fill helps understand how to mark and explore connected regions efficiently.

Epidemiology Spread Models

Exploring connected infected individuals in a population grid is like counting islands of infection.

Recognizing this connection shows how traversal algorithms model real-world spread phenomena.

Common Pitfalls

#1 Not marking visited cells causes infinite loops or double counting.

Wrong approach:

def dfs(r, c):
if grid[r][c] == '1':
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)

for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1

Correct approach:

def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)

for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1

Root cause:

Forgetting to mark visited cells or check boundaries leads to repeated visits and infinite recursion.

#2 Including diagonal neighbors without problem requirement changes results.

Wrong approach:

neighbors = [(1,0), (-1,0), (0,1), (0,-1), (1,1), (1,-1), (-1,1), (-1,-1)]

Correct approach:

neighbors = [(1,0), (-1,0), (0,1), (0,-1)]

Root cause:

Misunderstanding problem constraints about neighbor connectivity.

#3 Not checking grid boundaries before accessing neighbors causes errors.

Wrong approach:

if grid[r+1][c] == '1':
dfs(r+1, c)

Correct approach:

if 0 <= r+1 < rows and grid[r+1][c] == '1':
dfs(r+1, c)

Root cause:

Ignoring index limits leads to out-of-range errors.

Key Takeaways

Number of Islands counts connected groups of land cells in a grid using graph traversal.

DFS and BFS are interchangeable methods to explore and mark connected land cells.

Always mark visited cells and check grid boundaries to avoid errors and double counting.

Changing the grid in-place saves memory but modifies original data, which may not always be acceptable.

Understanding neighbor definitions (horizontal/vertical only) is crucial for correct island counting.

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