Number of Islands BFS and DFS in DSA Java - Build from Scratch

Number of Islands BFS and DFS

📖 Scenario: Imagine you have a map represented as a grid. Each cell in the grid is either land ('1') or water ('0'). You want to find out how many separate islands are on the map. An island is a group of connected lands horizontally or vertically.

🎯 Goal: You will write a Java program to count the number of islands in the grid using both Breadth-First Search (BFS) and Depth-First Search (DFS) methods.

📋 What You'll Learn

Create a 2D character array called grid with the exact values provided.

Create an integer variable rows to store the number of rows in grid.

Implement a method numIslandsDFS that uses DFS to count islands.

Implement a method numIslandsBFS that uses BFS to count islands.

Print the number of islands found by both methods.

💡 Why This Matters

🌍 Real World

Counting islands in a grid is similar to identifying connected regions in maps, satellite images, or game boards.

💼 Career

Understanding BFS and DFS is essential for software engineers working on graph problems, pathfinding, and spatial data analysis.

1

Create the grid data structure

Create a 2D character array called grid with these exact values:
{ {'1','1','0','0','0'}, {'1','1','0','0','0'}, {'0','0','1','0','0'}, {'0','0','0','1','1'} }

DSA Java

# Create the 2D char array grid with the given values
# Your code here

Hint

Use char[][] grid = { ... }; with the exact rows and columns as shown.

2

Add rows variable for grid size

Create an integer variable called rows and set it to the number of rows in grid.

DSA Java

char[][] grid = {
    {'1','1','0','0','0'},
    {'1','1','0','0','0'},
    {'0','0','1','0','0'},
    {'0','0','0','1','1'}
};
# Create int rows to store number of rows in grid
# Your code here

Hint

Use int rows = grid.length; to get the number of rows.

3

Implement DFS method to count islands

Write a method called numIslandsDFS that takes a 2D char array grid and returns an integer count of islands using Depth-First Search. Use helper method dfs to mark visited land cells as '0'. Use variables rows and cols for grid size. Iterate over each cell with for int r = 0; r < rows; r++ and for int c = 0; c < cols; c++. Increment count when land is found and call dfs.

DSA Java

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

int rows = grid.length;

// Implement numIslandsDFS method and dfs helper
// Your code here

Hint

Use nested loops to check each cell. When you find '1', increase count and call dfs to mark connected land.

4

Implement BFS method and print results

Write a method called numIslandsBFS that takes a 2D char array grid and returns an integer count of islands using Breadth-First Search. Use a queue to explore neighbors. Then, in the main method, print the results of numIslandsDFS(gridCopyForDFS) and numIslandsBFS(gridCopyForBFS) on copies of the original grid. Use System.out.println to print the counts exactly as:
"Number of islands (DFS): X"
and
"Number of islands (BFS): Y" where X and Y are the counts.

DSA Java

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

int rows = grid.length;

public static int numIslandsDFS(char[][] grid) {
    int rows = grid.length;
    if (rows == 0) return 0;
    int cols = grid[0].length;
    int count = 0;
    for (int r = 0; r = rows || c >= cols || grid[r][c] == '0') {
        return;
    }
    grid[r][c] = '0';
    dfs(grid, r - 1, c, rows, cols);
    dfs(grid, r + 1, c, rows, cols);
    dfs(grid, r, c - 1, rows, cols);
    dfs(grid, r, c + 1, rows, cols);
}

// Implement numIslandsBFS method and print results
// Your code here

Hint

Use a queue to explore neighbors in BFS. Print results exactly as shown.

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