Number of Islands BFS and DFS in DSA Java - Execution Trace

Concept Flow - Number of Islands BFS and DFS

Start: Grid with 0s and 1s

↓

Scan each cell

↓

Is cell '1' and not visited?

No→Move to next cell

Yes↓

Increment island count

↓

Run BFS or DFS to mark connected '1's as visited

↓

Mark all connected land as visited

↓

Continue scanning grid

↓

End: Return total island count

Scan each cell in the grid; when a land cell ('1') not visited is found, increase island count and use BFS or DFS to mark all connected land cells as visited; continue until all cells checked.

Execution Sample

DSA Java

int numIslands(char[][] grid) {
  int count = 0;
  for (int i = 0; i < grid.length; i++) {
    for (int j = 0; j < grid[0].length; j++) {
      if (grid[i][j] == '1') {
        count++;
        dfs(grid, i, j);
      }
    }
  }
  return count;
}

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

Counts islands by scanning grid and using DFS to mark connected land cells as visited.

Execution Table

Step	Operation	Cell Visited (i,j)	Island Count	Cells Marked Visited This Step	Grid State (Visual)
1	Check cell	(0,0)	0	None	[['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
2	Found '1', increment count and start DFS	(0,0)	1	(0,0)	[['0','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
3	DFS mark connected land	(0,1)	1	(0,1)	[['0','0','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
4	DFS mark connected land	(1,0)	1	(1,0)	[['0','0','0','0','0'], ['0','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
5	DFS mark connected land	(1,1)	1	(1,1)	[['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
6	Continue scanning	(0,1)	1	None	[['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
7	Continue scanning	(0,2)	1	None	[['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
8	Continue scanning	(2,1)	1	None	[['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
9	Found '1', increment count and start DFS	(2,2)	2	(2,2)	[['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','0','1','1']]
10	Continue scanning	(3,2)	2	None	[['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','0','1','1']]
11	Found '1', increment count and start DFS	(3,3)	3	(3,3)	[['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','0','0','1']]
12	DFS mark connected land	(3,4)	3	(3,4)	[['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','0','0','0']]
13	End scanning	N/A	3	None	[['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','0','0','0'], ['0','0','0','0','0']]

💡 All cells scanned; all islands counted and marked visited.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 12	Final
count	0	1	1	2	3	3
grid	Original grid	After marking first island visited	After marking first island visited	After marking second island visited	After marking third island visited	All zeros (visited)
current cell (i,j)	(0,0)	(1,1)	(2,2)	(3,4)	N/A	N/A

Key Moments - 3 Insights

Why do we mark visited cells by changing '1' to '0' in the grid?

Marking visited cells as '0' prevents revisiting the same land cell again, as shown in steps 2-5 where connected land cells are changed to '0' to avoid counting the same island multiple times.

Why do we increment the island count only when we find a '1' cell not visited?

Because each '1' cell not visited represents a new island start. The execution table rows 2, 9, and 11 show increments only when a new island is found.

How does DFS ensure all connected land cells are counted as one island?

DFS recursively visits all adjacent '1's and marks them visited, as seen in steps 3-5 and 12, so connected land is treated as one island.

Visual Quiz - 3 Questions

Look at the execution table at step 5, which cells have been marked visited?

A (0,0), (1,0), (1,1)

B (0,0), (0,1), (1,1)

C (0,0), (0,1), (1,0), (1,1)

D (0,0), (0,1), (1,0)

💡 Hint

Check the 'Cells Marked Visited This Step' and 'Grid State' columns for steps 2 to 5.

At which step does the island count increase to 3?

A Step 9

B Step 11

C Step 5

D Step 2

💡 Hint

Look at the 'Island Count' column in the execution table.

If we did not mark visited cells as '0', what would happen in the execution?

A The algorithm would count the same island multiple times.

B The island count would be correct.

C The algorithm would skip some islands.

D The grid would become empty immediately.

💡 Hint

Refer to the key moment about marking visited cells and steps 2-5.

Concept Snapshot

Number of Islands (BFS/DFS):
- Scan each cell in grid.
- If cell is '1', increment island count.
- Use DFS/BFS to mark all connected '1's as visited.
- Mark visited by changing '1' to '0'.
- Continue until all cells checked.
- Return total island count.

Full Transcript

The Number of Islands problem involves scanning a grid of '1's and '0's to count how many separate islands exist. We scan each cell; when we find a '1' that is not visited, we increase the island count and use DFS or BFS to mark all connected land cells as visited by changing them to '0'. This prevents counting the same island multiple times. We continue scanning until all cells are checked. The final count is the number of islands. The execution table shows step-by-step how cells are visited, marked, and how the island count changes. Key moments clarify why marking visited cells is necessary and how DFS covers connected land. The visual quiz tests understanding of these steps.

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