Number of Islands BFS and DFS in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start BFS from the given cell.

DSA Java

Queue<int[]> queue = new LinkedList<>();
queue.[1](new int[]{row, col});

Drag options to blanks, or click blank then click option'

Ainsert

Badd

Cpush

Doffer

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'push' which is for stacks, not queues.

Using 'insert' which is not a Queue method.

In Java's Queue interface, 'offer' is the preferred method to add elements safely.

2fill in blank

medium

Complete the code to mark the current cell as visited in DFS.

DSA Java

grid[row][col] = [1];

Drag options to blanks, or click blank then click option'

A'1'

B'0'

C'X'

D'#'

Attempts:

3 left

💡 Hint

Common Mistakes

Marking with '1' again which doesn't change the state.

Using '#' or 'X' which are not standard in this problem.

Marking the cell as '0' means water, so it won't be visited again.

3fill in blank

hard

Fix the error in the BFS neighbor check condition.

DSA Java

if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == [1]) {

Drag options to blanks, or click blank then click option'

A'0'

B'#'

C'1'

D'X'

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for '0' which is water, so BFS won't explore land.

Using '#' or 'X' which are not part of the grid representation.

We only add neighbors that are land cells marked '1' to the queue.

4fill in blank

hard

Fill both blanks to complete the DFS recursive calls for neighbors.

DSA Java

dfs(grid, row [1] 1, col);
dfs(grid, row, col [2] 1);

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction when addition is needed to move forward.

Using multiplication or division which are invalid for index movement.

We move to adjacent cells by adding or subtracting 1 from row or col.

5fill in blank

hard

Fill all three blanks to complete the BFS neighbor exploration loop.

DSA Java

int[] dr = [1];
int[] dc = [2];
for (int i = 0; i < 4; i++) {
    int nr = r + dr[i];
    int nc = c + dc[i];
    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == [3]) {
        queue.offer(new int[]{nr, nc});
        grid[nr][nc] = '0';
    }
}

Drag options to blanks, or click blank then click option'

Anew int[]{-1, 1, 0, 0}

Bnew int[]{0, 0, -1, 1}

C'1'

D'0'

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up dr and dc arrays.

Checking for '0' instead of '1' which skips land cells.

dr and dc arrays represent row and column changes for neighbors; we check for land '1' cells.

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