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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS-based Number of Islands

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

DSA Java

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int count = 0;
        int rows = grid.length, 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++;
                    java.util.Queue<int[]> queue = new java.util.LinkedList<>();
                    queue.offer(new int[]{r,c});
                    visited[r][c] = true;
                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        for (int[] d : directions) {
                            int nr = cell[0] + d[0], nc = cell[1] + 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 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'}
        };
        Solution sol = new Solution();
        System.out.println(sol.numIslands(grid));
    }
}

A 3

B 1

C 4

D 2

💡 Hint

Count connected groups of '1's using BFS.

The grid has three separate islands: top-left 2x2 block, middle single cell, and bottom-right 2 cells connected.

❓ Predict Output

intermediate

Output of DFS-based Number of Islands

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

DSA Java

public class Solution {
    private void dfs(char[][] grid, int r, int c, boolean[][] visited) {
        int rows = grid.length, 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, r+1, c, visited);
        dfs(grid, r-1, c, visited);
        dfs(grid, r, c+1, visited);
        dfs(grid, r, c-1, visited);
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int count = 0;
        int rows = grid.length, 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, r, c, visited);
                }
            }
        }
        return count;
    }

    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'}
        };
        Solution sol = new Solution();
        System.out.println(sol.numIslands(grid));
    }
}

A 3

B 2

C 1

D 4

💡 Hint

Use DFS to mark all connected land cells.

DFS explores each island fully, counting 3 islands in the grid.

🧠 Conceptual

advanced

Why BFS or DFS is suitable for Number of Islands?

Why do BFS and DFS work well to solve the Number of Islands problem?

A Because they convert the grid into a tree structure automatically.

B Because they sort the grid cells to find islands faster.

C Because they use hashing to store island coordinates.

D Because they explore all connected land cells systematically, marking visited to avoid recounting.

💡 Hint

Think about how connected components are found in graphs.

BFS and DFS traverse connected nodes (land cells) fully, marking them visited to count distinct islands.

🔧 Debug

advanced

Identify the bug in this DFS code for Number of Islands

What error will this DFS code cause when counting islands?

DSA Java

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

public int numIslands(char[][] grid) {
    int count = 0;
    int rows = grid.length, 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, r, c, visited);
            }
        }
    }
    return count;
}

A Incorrect count because count++ is inside DFS

B StackOverflowError due to missing visited check in DFS base case

C NullPointerException because visited array is not initialized

D No error, code works correctly

💡 Hint

Check the DFS base case conditions carefully.

The DFS does not check if a cell is already visited before recursing, causing infinite recursion.

🚀 Application

expert

Optimizing Number of Islands with Union-Find

Which statement about using Union-Find (Disjoint Set) to solve Number of Islands is true?

A Union-Find cannot handle diagonal connections between land cells.

B Union-Find is slower than DFS because it uses recursion heavily.

C Union-Find can efficiently merge connected land cells and count distinct sets representing islands.

D Union-Find requires converting the grid into a binary tree first.

💡 Hint

Think about how Union-Find groups connected components.

Union-Find merges connected land cells into sets, allowing quick counting of distinct islands without recursion.

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