Number of Islands BFS and DFS in DSA Javascript

Mental Model

We find groups of connected land cells in a grid by exploring neighbors until the whole island is visited.

Analogy: Imagine walking through a forest where each tree is connected by paths. Once you find a tree, you explore all connected trees before moving to the next forest patch.

Grid example:
1 1 0 0 0
1 1 0 0 1
0 0 0 1 1
0 0 0 0 0
1 0 1 0 1

1 = land, 0 = water

Dry Run Walkthrough

Input: grid = [[1,1,0,0,0],[1,1,0,0,1],[0,0,0,1,1],[0,0,0,0,0],[1,0,1,0,1]]

Goal: Count how many separate islands (groups of connected 1s) are in the grid

Step 1: Start scanning from top-left; find first land at (0,0), start BFS to mark this island

[1,1,0,0,0]
[1,1,0,0,1]
[0,0,0,1,1]
[0,0,0,0,0]
[1,0,1,0,1]
Visited: (0,0)

Why: We found the first island's starting point to explore all connected land

Step 2: BFS visits neighbors (0,1), (1,0), (1,1) marking them visited

[V,V,0,0,0]
[V,V,0,0,1]
[0,0,0,1,1]
[0,0,0,0,0]
[1,0,1,0,1]
Visited: (0,0),(0,1),(1,0),(1,1)

Why: Marking all connected land cells to count as one island

Step 3: Continue scanning grid; find next unvisited land at (1,4), start BFS for second island

[V,V,0,0,0]
[V,V,0,0,V]
[0,0,0,1,1]
[0,0,0,0,0]
[1,0,1,0,1]
Visited: previous + (1,4)

Why: Found a new island separate from the first

Step 4: BFS visits neighbors (2,4), (2,3) marking them visited

[V,V,0,0,0]
[V,V,0,0,V]
[0,0,0,V,V]
[0,0,0,0,0]
[1,0,1,0,1]
Visited: previous + (2,3),(2,4)

Why: Marking all connected land cells of second island

Step 5: Continue scanning; find land at (4,0), mark visited as third island

[V,V,0,0,0]
[V,V,0,0,V]
[0,0,0,V,V]
[0,0,0,0,0]
[V,0,1,0,1]
Visited: previous + (4,0)

Why: New isolated land cell is a separate island

Step 6: Find land at (4,2), mark visited as fourth island

[V,V,0,0,0]
[V,V,0,0,V]
[0,0,0,V,V]
[0,0,0,0,0]
[V,0,V,0,1]
Visited: previous + (4,2)

Why: Another isolated land cell forms a new island

Step 7: Find land at (4,4), mark visited as fifth island

[V,V,0,0,0]
[V,V,0,0,V]
[0,0,0,V,V]
[0,0,0,0,0]
[V,0,V,0,V]
Visited: previous + (4,4)

Why: Last isolated land cell is a separate island

Result:

Visited all islands.
Final count: 5 islands

Annotated Code

DSA Javascript

class Solution {
  numIslands(grid) {
    if (!grid || grid.length === 0) return 0;
    const rows = grid.length;
    const cols = grid[0].length;
    let count = 0;
    const visited = Array.from({ length: rows }, () => Array(cols).fill(false));

    const directions = [[1,0],[-1,0],[0,1],[0,-1]];

    const bfs = (r, c) => {
      const queue = [];
      queue.push([r, c]);
      visited[r][c] = true;

      while (queue.length > 0) {
        const [row, col] = queue.shift();
        for (const [dr, dc] of directions) {
          const nr = row + dr;
          const nc = col + dc;
          if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
              !visited[nr][nc] && grid[nr][nc] === 1) {
            queue.push([nr, nc]);
            visited[nr][nc] = true;
          }
        }
      }
    };

    for (let r = 0; r < rows; r++) {
      for (let c = 0; c < cols; c++) {
        if (grid[r][c] === 1 && !visited[r][c]) {
          bfs(r, c);
          count++;
        }
      }
    }
    return count;
  }
}

// Driver code
const grid = [
  [1,1,0,0,0],
  [1,1,0,0,1],
  [0,0,0,1,1],
  [0,0,0,0,0],
  [1,0,1,0,1]
];
const sol = new Solution();
console.log(sol.numIslands(grid));

if (grid[r][c] === 1 && !visited[r][c]) {

Check if current cell is unvisited land to start BFS

bfs(r, c);

Start BFS to mark all connected land cells as visited

visited[r][c] = true;

Mark starting cell visited to avoid revisiting

while (queue.length > 0) {

Process all cells in current island's BFS queue

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

Check neighbor is inside grid, unvisited, and land before adding to queue

count++;

Increment island count after fully exploring one island

Output

5

Complexity Analysis

Time: O(m*n) because each cell is visited once during BFS or DFS

Space: O(m*n) for the visited array and BFS queue in worst case

vs Alternative: Compared to checking each cell and scanning neighbors repeatedly, BFS/DFS marks connected land once, avoiding repeated work

Edge Cases

Empty grid

Returns 0 since no islands exist

DSA Javascript

if (!grid || grid.length === 0) return 0;

Grid with all water (0s)

Returns 0 as no land cells to form islands

DSA Javascript

if (grid[r][c] === 1 && !visited[r][c]) {

Grid with all land (1s)

Returns 1 since all land is connected as one big island

DSA Javascript

visited[r][c] = true;

When to Use This Pattern

When you need to count connected groups in a grid, use BFS or DFS to explore neighbors and mark visited cells to avoid double counting.

Common Mistakes

Mistake: Not marking visited cells, causing infinite loops or overcounting islands
Fix: Always mark cells as visited when adding to BFS/DFS queue

Mistake: Checking neighbors outside grid boundaries causing errors
Fix: Add boundary checks before accessing neighbors

Summary

Counts how many separate islands of connected land exist in a grid using BFS or DFS.

Use when you need to find connected components in a 2D grid or map.

The key is to explore all connected land from one cell before moving to the next unvisited land.

Practice

1. What does the "Number of Islands" problem ask you to find in a grid of '1's and '0's?

easy

A. Count how many groups of connected '1's (islands) are in the grid

B. Find the largest island size in the grid

C. Calculate the total number of '0's in the grid

D. Replace all '1's with '0's in the grid

Solution

1. Step 1: Understand the grid representation

   The grid contains '1's representing land and '0's representing water.

2. Step 2: Identify what an island means

   An island is a group of connected '1's horizontally or vertically.

3. Final Answer:

   Count how many groups of connected '1's (islands) are in the grid -> Option A

4. Quick Check:

   Number of islands = count of connected '1' groups [OK]

Hint: Islands = connected '1's groups, count them [OK]

Common Mistakes:

• Confusing island count with largest island size
• Counting '0's instead of '1's
• Ignoring connectivity rules (only horizontal/vertical)

2. Which of the following is the correct way to start a DFS function in JavaScript for the Number of Islands problem?

easy

A. function dfs(grid, r, c) { if (r < 0 || c < 0) return; }

B. function dfs(grid, r, c) { if (r <= 0 || c <= 0 || r > grid.length || c > grid[0].length) return; }

C. function dfs(grid, r, c) { if (r > grid.length || c > grid[0].length) return; }

D. function dfs(grid, r, c) { if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return; }

Solution

1. Step 1: Check boundary conditions for DFS

   We must stop DFS if row or column is outside grid bounds.

2. Step 2: Write correct boundary check

   Row or column less than 0 or greater or equal to grid size means out of bounds.

3. Final Answer:

   function dfs(grid, r, c) { if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return; } -> Option D

4. Quick Check:

   Boundary check includes all invalid indices [OK]

Hint: Check all out-of-bound indices with < 0 or >= length [OK]

Common Mistakes:

• Using > instead of >= for boundary check
• Missing some boundary conditions
• Using <= 0 which excludes valid index 0

3. What will be the output of the following code snippet for the grid below?

const grid = [ ['1','1','0','0'], ['1','0','0','1'], ['0','0','1','1'], ['0','0','0','0'] ]; function numIslands(grid) { let count = 0; const dfs = (r, c) => { if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] === '0') return; grid[r][c] = '0'; dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1); }; for (let r = 0; r < grid.length; r++) { for (let c = 0; c < grid[0].length; c++) { if (grid[r][c] === '1') { dfs(r, c); count++; } } } return count; } console.log(numIslands(grid));

medium

A. 1

B. 3

C. 2

D. 4

Solution

1. Step 1: Identify islands in the grid

   Islands are groups of connected '1's. Here, islands are: top-left (3 cells: (0,0),(0,1),(1,0)), single cell at (1,3), and bottom cluster (2 cells: (2,2),(2,3)). Total islands = 3.

2. Step 2: Count islands using DFS

   DFS marks visited '1's as '0'. After visiting each island, count increments. Total islands counted = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Count connected '1' groups = 3 [OK]

Hint: Count connected '1' groups by marking visited [OK]

Common Mistakes:

• Counting diagonal connections as islands
• Not marking visited cells, causing overcount
• Misreading grid layout

4. The following BFS code for Number of Islands has a bug. What is the bug?

function bfs(grid, r, c) { const queue = [[r, c]]; while (queue.length > 0) { const [row, col] = queue.shift(); if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length || grid[row][col] === '0') continue; grid[row][col] = '0'; queue.push([row + 1, col]); queue.push([row - 1, col]); queue.push([row, col + 1]); queue.push([row, col - 1]); } }

medium

A. It does not check if a cell is already visited before pushing neighbors

B. It marks visited cells after adding neighbors to queue

C. It uses queue.shift() which is inefficient for large grids

D. It uses recursion instead of iteration

Solution

1. Step 1: Analyze neighbor addition in BFS

   The code adds neighbors to the queue without checking if they are visited or water.

2. Step 2: Identify consequence of missing check

   This causes multiple visits to the same cell, increasing runtime and possible infinite loops.

3. Final Answer:

   It does not check if a cell is already visited before pushing neighbors -> Option A

4. Quick Check:

   Check before enqueueing neighbors to avoid repeats [OK]

Hint: Check visited before enqueueing neighbors in BFS [OK]

Common Mistakes:

• Thinking queue.shift() inefficiency is the bug here
• Marking visited after enqueue instead of before
• Confusing recursion with iteration

5. Given a grid where diagonal connections also count as connected land, how would you modify the DFS to count islands correctly?

hard

A. Ignore diagonal neighbors and count only vertical connections

B. Only check horizontal neighbors (r,c+1) and (r,c-1)

C. Add diagonal neighbors (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) to DFS calls

D. Use BFS instead of DFS without changing neighbors

Solution

1. Step 1: Understand connectivity rules

   Diagonal connections mean neighbors include diagonals, not just up/down/left/right.

2. Step 2: Modify DFS to include diagonal neighbors

   Add DFS calls for (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) along with existing neighbors.

3. Final Answer:

   Add diagonal neighbors (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) to DFS calls -> Option C

4. Quick Check:

   Include diagonal neighbors for diagonal connectivity [OK]

Hint: Add diagonal neighbors to DFS for diagonal island counting [OK]

Common Mistakes:

• Ignoring diagonal neighbors when required
• Switching BFS/DFS without changing neighbor logic
• Counting only horizontal or vertical neighbors