Number of Islands BFS and DFS in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS-based Number of Islands

What is the output of the following JavaScript code that counts islands using BFS?

DSA Javascript

function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  const directions = [[1,0],[-1,0],[0,1],[0,-1]];

  function bfs(r, c) {
    const queue = [];
    queue.push([r, c]);
    grid[r][c] = '0';
    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 && grid[nr][nc] === '1') {
          queue.push([nr, nc]);
          grid[nr][nc] = '0';
        }
      }
    }
  }

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

const grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
];
console.log(numIslands(grid));

A 3

B 2

C 4

D 1

💡 Hint

Count how many separate groups of connected '1's are in the grid.

The BFS explores each island fully and marks visited cells as '0'. The grid has three separate islands: one big in top-left, one single cell in middle, and one connected pair in bottom-right.

❓ Predict Output

intermediate

Output of DFS-based Number of Islands

What is the output of this JavaScript code that counts islands using DFS?

DSA Javascript

function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || 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 < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        dfs(r, c);
        count++;
      }
    }
  }
  return count;
}

const grid = [
  ['1','1','1','0','0'],
  ['1','1','0','0','1'],
  ['0','0','0','1','1'],
  ['0','0','0','0','0']
];
console.log(numIslands(grid));

A 2

B 3

C 1

D 4

💡 Hint

DFS visits all connected land cells recursively.

The DFS marks connected '1's as '0'. The grid has two islands: one large top-left cluster, and one cluster in the middle-right connected via (1,4)-(2,4)-(2,3).

🔧 Debug

advanced

Identify the error in BFS island counting code

What error will this code produce when run, and why?

DSA Javascript

function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  const directions = [[1,0],[-1,0],[0,1],[0,-1]];

  function bfs(r, c) {
    const queue = [];
    queue.push([r, c]);
    grid[r][c] = '0';
    while (queue.length > 0) {
      const [row, col] = queue.pop();
      for (const [dr, dc] of directions) {
        const nr = row + dr;
        const nc = col + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
          queue.push([nr, nc]);
          grid[nr][nc] = '0';
        }
      }
    }
  }

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

const grid = [
  ['1','1','0'],
  ['0','1','0'],
  ['1','0','1']
];
console.log(numIslands(grid));

A TypeError because queue is undefined

B The code runs correctly and outputs 3

C SyntaxError due to missing semicolon

D The code outputs 2 because BFS uses pop() instead of shift() causing DFS behavior

💡 Hint

Check how queue is used in BFS loop.

The code runs correctly and outputs 3. queue.pop() implements iterative DFS (LIFO stack) instead of BFS (FIFO queue), but cell marking on enqueue ensures all connected cells are visited correctly regardless of order.

❓ Predict Output

advanced

Output of DFS with diagonal connections

What is the output of this code counting islands using DFS considering diagonal neighbors as connected?

DSA Javascript

function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  const directions = [[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]];

  function dfs(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return;
    grid[r][c] = '0';
    for (const [dr, dc] of directions) {
      dfs(r + dr, c + dc);
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        dfs(r, c);
        count++;
      }
    }
  }
  return count;
}

const grid = [
  ['1','0','1'],
  ['0','1','0'],
  ['1','0','1']
];
console.log(numIslands(grid));

A 3

B 5

C 1

D 4

💡 Hint

Diagonal neighbors connect islands here.

Because diagonal neighbors count, all '1's connect into one big island.

🧠 Conceptual

expert

Time complexity of Number of Islands algorithms

What is the time complexity of both BFS and DFS approaches to solve the Number of Islands problem on an m x n grid?

A O(1) because the grid size is fixed

B O((m * n)^2) because BFS and DFS explore neighbors repeatedly

C O(m + n) because traversal depends on rows and columns separately

D O(m * n) because each cell is visited once during traversal

💡 Hint

Consider how many times each cell is processed.

Each cell is visited once and marked visited, so total work is proportional to number of cells, O(m*n).

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