Number of Islands BFS and DFS in DSA Java - Time & Space Complexity

Time Complexity: Number of Islands BFS and DFS

O(m x n)

Understanding Time Complexity

We want to understand how the time needed to find islands grows as the grid size increases.

How does the search through the grid affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public 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') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') {
        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);
}

This code counts islands by visiting each cell and exploring connected land cells using DFS.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each cell once and exploring connected neighbors via DFS.
• How many times: Outer loops run over all cells (rows x columns). DFS visits connected land cells once each.

How Execution Grows With Input

As the grid size grows, the total work grows roughly with the number of cells.

Input Size (n = rows x columns)	Approx. Operations
10 x 10 = 100	About 100 visits
100 x 100 = 10,000	About 10,000 visits
1000 x 1000 = 1,000,000	About 1,000,000 visits

Pattern observation: The work grows linearly with the total number of cells in the grid.

Final Time Complexity

Time Complexity: O(m x n)

This means the time grows linearly with the total number of cells in the grid.

Common Mistake

[X] Wrong: "DFS runs multiple times on the same cells, so time is more than linear."

[OK] Correct: Each cell is visited once and marked visited, so DFS does not repeat work on the same cell.

Interview Connect

Understanding this helps you explain how graph traversal works on grids and shows you can analyze nested loops with recursion clearly.

Self-Check

"What if we used BFS instead of DFS? How would the time complexity change?"

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