Number of Islands BFS and DFS in DSA Java - 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. Two land cells are connected if they are next to each other horizontally or vertically. BFS (Breadth-First Search) and DFS (Depth-First Search) are two ways to explore these connected cells to find each island.

Why it matters

This problem helps us understand how to explore connected areas in a grid, which is useful in many real-world tasks like finding clusters in maps, analyzing networks, or image processing. Without this concept, we would struggle to identify separate groups or regions efficiently in data that looks like a grid.

Where it fits

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

Mental Model

Core Idea

To count islands, explore each land cell and mark all connected land cells as visited using BFS or DFS, so each island is counted once.

Think of it like...

Imagine a map with patches of forest (land) and lakes (water). To count how many forests there are, you start at one tree and walk through all connected trees until you reach water or edges, then move to the next unvisited tree to find another forest.

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 (cells with 1s connected)
  Island 2: middle-right cluster
  Island 3: bottom-left single cell (row 4, col 0)
  Island 4: bottom-middle single cell (row 4, col 2)
  Island 5: bottom-right single cell (row 4, col 4)

Traversal flow:

Start at (0,0) -> visit connected land cells -> mark visited
Move to next unvisited land cell -> repeat

Build-Up - 7 Steps

1

Foundation

Understanding the Grid and Islands

Concept: Introduce the grid structure and what counts as an island.

A grid is a 2D array where each cell is either '1' (land) or '0' (water). An island is a group of '1's connected horizontally or vertically. Diagonal connections do not count. The goal is to count how many such islands exist.

Result

You know what the input looks like and what the problem asks: count groups of connected land cells.

Understanding the problem setup is crucial before trying to solve it; knowing what counts as connected land defines the problem boundaries.

2

Foundation

Basic Traversal with Visited Tracking

Concept: Learn to visit cells and mark them to avoid counting twice.

To avoid counting the same land cell multiple times, we keep track of visited cells. When we find a land cell, we mark it visited and explore its neighbors. This prevents infinite loops and double counting.

Result

You can now safely explore parts of the grid without revisiting the same cells.

Tracking visited cells is the foundation of all graph and grid traversal algorithms to ensure correctness and efficiency.

3

Intermediate

Depth-First Search (DFS) for Island Counting

🤔Before reading on: do you think DFS explores neighbors by going deep first or wide first? Commit to your answer.

Concept: Use DFS to explore all connected land cells starting from one cell, marking them visited.

DFS uses recursion or a stack to explore as far as possible along one branch before backtracking. For each land cell, recursively visit its unvisited neighbors (up, down, left, right). This marks the entire island.

Result

After DFS from one land cell, all connected land cells of that island are marked visited, so the island is counted once.

Understanding DFS helps you see how deep exploration can efficiently mark connected components in a grid.

4

Intermediate

Breadth-First Search (BFS) for Island Counting

🤔Before reading on: do you think BFS explores neighbors level by level or goes deep first? Commit to your answer.

Concept: Use BFS to explore all connected land cells starting from one cell, marking them visited.

BFS uses a queue to explore neighbors level by level. Starting from a land cell, add it to the queue, then repeatedly remove a cell, visit its unvisited neighbors, and add them to the queue. This continues until the entire island is visited.

Result

After BFS from one land cell, all connected land cells of that island are marked visited, so the island is counted once.

Knowing BFS shows a different way to explore connected cells, useful when you want to process neighbors in order of closeness.

5

Intermediate

Implementing Island Counting Algorithm

🤔Before reading on: do you think you should start BFS/DFS from every cell or only land cells? Commit to your answer.

Concept: Combine traversal and visited tracking to count islands by scanning the grid.

Loop through each cell in the grid. When you find an unvisited land cell, start BFS or DFS from it to mark the entire island visited. Increase the island count by one. Continue until all cells are checked.

Result

You get the total number of islands in the grid after scanning all cells.

Knowing when and where to start BFS/DFS is key to counting islands correctly and efficiently.

6

Advanced

Handling Edge Cases and Grid Boundaries

🤔Before reading on: do you think checking neighbors outside the grid causes errors? Commit to your answer.

Concept: Learn to safely check neighbors without going outside the grid limits.

When exploring neighbors, always check if the neighbor's row and column are within grid bounds. Skip neighbors that are out of bounds or water cells. This prevents errors and infinite loops.

Result

Your algorithm runs safely on any grid size without crashing or incorrect counts.

Proper boundary checks prevent runtime errors and ensure the algorithm works on all inputs.

7

Expert

Optimizing Space and Time Complexity

🤔Before reading on: do you think BFS and DFS have the same time complexity for this problem? Commit to your answer.

Concept: Analyze and optimize the algorithm's efficiency and memory use.

Both BFS and DFS visit each cell once, so time complexity is O(m*n) for an m by n grid. Space complexity depends on the maximum size of the queue or recursion stack. Using iterative DFS with a stack can avoid recursion limits. Also, modifying the input grid to mark visited cells can save extra space.

Result

You understand how to write efficient and safe code for large grids.

Knowing complexity helps you choose the right approach for performance and resource constraints.

Under the Hood

The grid is treated like a graph where each cell is a node connected to up to four neighbors. BFS uses a queue to explore neighbors in layers, while DFS uses recursion or a stack to explore deeply before backtracking. Marking visited cells prevents revisiting nodes and infinite loops. The traversal continues until all connected nodes of an island are visited, effectively isolating each island as a connected component.

Why designed this way?

BFS and DFS are classic graph traversal methods chosen because grids can be seen as graphs. They are simple, well-understood, and efficient for exploring connected components. Alternatives like Union-Find exist but are more complex. BFS and DFS provide clear, step-by-step exploration that matches the problem's needs.

Grid as graph:

  [0,0]--[0,1]   [0,2]   [0,3]
    |      |      |       |
  [1,0]--[1,1]   [1,2]   [1,3]

Traversal flow:

Start at [0,0]
  |
  v
Visit neighbors [0,1], [1,0]
  |
  v
Continue until all connected nodes visited

Queue (BFS) or Stack (DFS) manages next nodes to visit.

Myth Busters - 4 Common Misconceptions

Quick: Do you think diagonal cells count as connected land? Commit yes or no.

Common Belief: Diagonal neighbors are part of the same island.

Reality: Only horizontal and vertical neighbors count as connected land; diagonals do not connect islands.

Why it matters: Counting diagonals would merge separate islands incorrectly, leading to wrong island counts.

Quick: Do you think you must start BFS/DFS from every cell, even water? Commit yes or no.

Common Belief: You need to run BFS/DFS from every cell to find islands.

Reality: You only start BFS/DFS from unvisited land cells; water cells are ignored.

Why it matters: Starting from water wastes time and can cause incorrect logic or errors.

Quick: Do you think BFS is always faster than DFS for this problem? Commit yes or no.

Common Belief: BFS is always faster than DFS for counting islands.

Reality: Both BFS and DFS have the same time complexity and similar performance; choice depends on implementation and constraints.

Why it matters: Choosing BFS just for speed may not improve performance and can increase memory use.

Quick: Do you think marking visited cells is optional? Commit yes or no.

Common Belief: You can count islands without marking visited cells.

Reality: Marking visited cells is essential to avoid counting the same island multiple times and to prevent infinite loops.

Why it matters: Without marking visited, the algorithm may run forever or give wrong counts.

Expert Zone

1

Using the input grid itself to mark visited cells saves extra memory but modifies input, which may not be allowed in some cases.

2

Iterative DFS with a stack avoids recursion depth limits that can cause stack overflow in large grids.

3

BFS can be more memory-intensive than DFS because it stores all neighbors at the current level, which can be large in dense islands.

When NOT to use

For very large grids or when input modification is forbidden, consider Union-Find data structure for better control. Also, if diagonal connections matter, BFS/DFS must be adapted or replaced with other methods.

Production Patterns

In real systems, this pattern is used in image segmentation, network cluster detection, and map region analysis. Often combined with preprocessing steps and optimized with iterative DFS to handle large data efficiently.

Connections

Graph Connected Components

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

Understanding islands as connected components helps apply graph theory tools and algorithms broadly.

Flood Fill Algorithm

Flood fill uses similar BFS/DFS traversal to fill connected areas in graphics.

Knowing flood fill clarifies how BFS/DFS can be used to process connected regions beyond counting.

Epidemiology Spread Models

Spread of infection in a population can be modeled as BFS/DFS on a grid or network.

Recognizing BFS/DFS in disease spread models shows how these algorithms help understand real-world processes.

Common Pitfalls

#1 Not checking grid boundaries before accessing neighbors.

Wrong approach:

if (grid[r+1][c] == '1') { dfs(r+1, c); }

Correct approach:

if (r+1 < grid.length && grid[r+1][c] == '1') { dfs(r+1, c); }

Root cause:

Assuming neighbors always exist leads to index out of bounds errors.

#2 Starting DFS/BFS from water cells or already visited land cells.

Wrong approach:

for each cell: dfs(r, c) without checking if it's land and unvisited.

Correct approach:

for each cell: if (grid[r][c] == '1' && not visited) dfs(r, c);

Root cause:

Not filtering starting points causes redundant work and incorrect counts.

#3 Not marking cells as visited after visiting.

Wrong approach:

dfs(r, c) without marking grid[r][c] or visited array.

Correct approach:

mark grid[r][c] as visited before recursive calls.

Root cause:

Leads to infinite recursion or counting the same island multiple times.

Key Takeaways

Number of Islands problem counts connected groups of land cells in a grid using BFS or DFS.

Marking visited cells is essential to avoid revisiting and double counting.

DFS explores deeply along one path before backtracking, while BFS explores neighbors level by level.

Proper boundary checks prevent errors and ensure the algorithm works on all grid sizes.

Both BFS and DFS have similar time complexity; choice depends on constraints like recursion limits and memory.

Practice

1. What does the "Number of Islands" problem ask you to find in a 2D grid of '1's (land) and '0's (water)?

easy

A. Determine if the grid contains any water cells

B. Count how many separate groups of connected lands (islands) exist

C. Calculate the total number of '1's in the grid

D. Find the largest island size

Solution

1. Step 1: Understand the problem goal

   The problem asks to count distinct islands, where islands are groups of connected '1's horizontally or vertically.

2. Step 2: Clarify what to count

   We count how many such groups exist, not their sizes or total land cells.

3. Final Answer:

   Count how many separate groups of connected lands (islands) exist -> Option B

4. Quick Check:

   Number of islands = count of connected land groups [OK]

Hint: Islands = connected land groups, count them [OK]

Common Mistakes:

• Counting total land cells instead of groups
• Including diagonal connections as connected
• Confusing largest island size with count

2. Which of the following Java code snippets correctly initializes a queue for BFS traversal in the Number of Islands problem?

easy

A. Queue queue = new LinkedList<>();

B. Queue queue = new Queue();

C. LinkedList queue = new Queue<>();

D. Queue<int> queue = new ArrayList<>();

Solution

1. Step 1: Identify correct queue initialization

   In Java, Queue is an interface; LinkedList implements Queue. So, Queue queue = new LinkedList<>(); is correct.

2. Step 2: Check other options for errors

   Queue queue = new Queue(); uses 'new Queue()' which is invalid (Queue is interface). LinkedList queue = new Queue<>(); reverses types. Queue<int> queue = new ArrayList<>(); uses ArrayList which does not implement Queue.

3. Final Answer:

   Queue queue = new LinkedList<>(); -> Option A

4. Quick Check:

   Queue interface + LinkedList implementation = correct [OK]

Hint: Use Queue interface with LinkedList for BFS queue [OK]

Common Mistakes:

• Trying to instantiate interface Queue directly
• Using ArrayList instead of a Queue implementation
• Wrong generic types for queue elements

3. Given the grid:

char[][] grid = {
  {'1','1','0','0','0'},
  {'1','1','0','0','0'},
  {'0','0','1','0','0'},
  {'0','0','0','1','1'}
};

What is the output of a correct Number of Islands BFS or DFS implementation on this grid?

medium

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Identify islands in the grid

   First island: top-left 2x2 block of '1's. Second island: single '1' at grid[2][2]. Third island: bottom-right 2 connected '1's.

2. Step 2: Count total islands

   There are 3 separate islands in total.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count distinct connected land groups = 3 [OK]

Hint: Count connected land clusters, not individual cells [OK]

Common Mistakes:

• Counting diagonal connections as connected
• Missing single-cell islands
• Counting total '1's instead of groups

4. Consider this DFS code snippet for Number of Islands:

void dfs(char[][] grid, int r, int c) {
  if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0')
    return;
  grid[r][c] = '0';
  dfs(grid, r + 1, c);
  dfs(grid, r - 1, c);
  dfs(grid, r, c + 1);
  dfs(grid, r, c - 1);
}

What is the main bug if the grid is empty (zero rows)?

medium

A. IndexOutOfBoundsException when accessing grid[0].length

B. StackOverflowError due to infinite recursion

C. NullPointerException because grid is null

D. No bug, code works fine for empty grid

Solution

1. Step 1: Analyze grid access for empty grid

   If grid has zero rows, grid.length == 0, so grid[0] access causes IndexOutOfBoundsException.

2. Step 2: Identify cause of exception

   Accessing grid[0].length without checking grid length first causes error.

3. Final Answer:

   IndexOutOfBoundsException when accessing grid[0].length -> Option A

4. Quick Check:

   Empty grid means grid[0] invalid access [OK]

Hint: Check grid length before accessing grid[0] [OK]

Common Mistakes:

• Assuming grid always has at least one row
• Ignoring boundary checks before accessing grid[0]
• Confusing NullPointerException with IndexOutOfBoundsException

5. You want to modify the Number of Islands BFS solution to also return the size of the largest island. Which approach correctly extends BFS to achieve this?

hard

A. Count total '1's in grid before BFS and return that as largest island size

B. Run BFS once and multiply number of islands by 2 to estimate largest size

C. During BFS, count cells visited per island and track max count across islands

D. Use DFS instead of BFS because BFS cannot count island size

Solution

1. Step 1: Understand BFS traversal per island

   BFS visits all connected land cells of one island. Counting visited cells during BFS gives island size.

2. Step 2: Track largest island size

   Keep a max variable updated with the largest count found after each BFS traversal.

3. Final Answer:

   During BFS, count cells visited per island and track max count across islands -> Option C

4. Quick Check:

   Count cells per BFS, track max size [OK]

Hint: Count cells during BFS, update max size [OK]

Common Mistakes:

• Counting total land cells instead of per island
• Assuming BFS cannot count sizes
• Estimating size without traversal