Number of Islands BFS and DFS in DSA Java

Mental Model

We find groups of connected land cells in a grid by exploring neighbors until all connected parts are visited.

Analogy: Imagine islands on a map where you walk around each island fully before moving to the next one, marking visited spots so you don't count the same island twice.

Grid example:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

1 = land, 0 = water

Dry Run Walkthrough

Input: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]

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

Step 1: Start at (0,0), find land, begin BFS/DFS to mark connected land

[1↑,1,0,0,0]
[1,1,0,0,0]
[0,0,1,0,0]
[0,0,0,1,1]

Why: We found the first island starting point

Step 2: Visit neighbors of (0,0): (0,1) and (1,0) are land, mark visited

[X,X,0,0,0]
[X,1,0,0,0]
[0,0,1,0,0]
[0,0,0,1,1]

Why: Mark connected land to avoid recounting

Step 3: Visit neighbor (1,1), mark visited

[X,X,0,0,0]
[X,X,0,0,0]
[0,0,1,0,0]
[0,0,0,1,1]

Why: Complete marking first island

Step 4: Move to next unvisited land at (2,2), start BFS/DFS for second island

[X,X,0,0,0]
[X,X,0,0,0]
[0,0,↑1,0,0]
[0,0,0,1,1]

Why: Found second island

Step 5: Mark (2,2) visited, no connected neighbors

[X,X,0,0,0]
[X,X,0,0,0]
[0,0,X,0,0]
[0,0,0,1,1]

Why: Second island is a single cell

Step 6: Move to next unvisited land at (3,3), start BFS/DFS for third island

[X,X,0,0,0]
[X,X,0,0,0]
[0,0,X,0,0]
[0,0,0,↑1,1]

Why: Found third island

Step 7: Mark (3,3) and (3,4) visited as connected land

[X,X,0,0,0]
[X,X,0,0,0]
[0,0,X,0,0]
[0,0,0,X,X]

Why: Complete marking third island

Result:

[X,X,0,0,0]
[X,X,0,0,0]
[0,0,X,0,0]
[0,0,0,X,X]
Number of islands = 3

Annotated Code

DSA Java

import java.util.LinkedList;
import java.util.Queue;

public class NumberOfIslands {

    public static int numIslandsBFS(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int count = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];

        int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    count++;
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{r,c});
                    visited[r][c] = true;

                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        int row = cell[0], col = cell[1];
                        for (int[] d : directions) {
                            int nr = row + d[0], nc = col + d[1];
                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                                grid[nr][nc] == '1' && !visited[nr][nc]) {
                                queue.offer(new int[]{nr,nc});
                                visited[nr][nc] = true;
                            }
                        }
                    }
                }
            }
        }
        return count;
    }

    public static int numIslandsDFS(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int count = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    count++;
                    dfs(grid, visited, r, c);
                }
            }
        }
        return count;
    }

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

    public static void main(String[] args) {
        char[][] grid = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };

        System.out.println("Number of islands (BFS): " + numIslandsBFS(grid));
        System.out.println("Number of islands (DFS): " + numIslandsDFS(grid));
    }
}

if (grid[r][c] == '1' && !visited[r][c]) { count++; queue.offer(new int[]{r,c}); visited[r][c] = true; }

Start BFS from unvisited land cell and mark it visited

while (!queue.isEmpty()) { ... for each neighbor if land and unvisited, add to queue and mark visited }

Explore all connected land cells in BFS manner

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

Start DFS from unvisited land cell and mark connected land

dfs(grid, visited, r - 1, c); dfs(grid, visited, r + 1, c); dfs(grid, visited, r, c - 1); dfs(grid, visited, r, c + 1);

Recursively visit all connected neighbors in DFS

Output

Number of islands (BFS): 3

Number of islands (DFS): 3

Complexity Analysis

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

Space: O(m*n) for the visited array and BFS queue or DFS recursion stack in worst case

vs Alternative: This is more efficient than checking each cell multiple times; naive approach might repeatedly scan neighbors causing higher cost

Edge Cases

Empty grid

Returns 0 islands immediately

DSA Java

if (grid == null || grid.length == 0) return 0;

Grid with all water (0s)

No islands found, returns 0

DSA Java

if (grid[r][c] == '1' && !visited[r][c])

Grid with one big island (all 1s)

Returns 1 after marking all connected land

DSA Java

visited[r][c] = true;

When to Use This Pattern

When asked to count connected groups in a grid, use BFS or DFS to explore neighbors and mark visited to avoid double counting.

Common Mistakes

Mistake: Not marking visited cells, causing infinite loops or overcounting
Fix: Mark each visited land cell immediately when discovered

Mistake: Checking neighbors outside grid boundaries
Fix: Add boundary checks before accessing neighbors

Summary

Counts how many separate islands of connected land cells exist in a grid.

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

The key is to explore all connected neighbors from each unvisited land cell to mark the entire island.

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