Number of Islands BFS and DFS in DSA Javascript - Deep Dive

Overview - Number of Islands BFS and DFS

What is it?

Number of Islands is a problem where you count how many separate groups of connected 'land' cells exist in a grid. Each cell can be water or land, and connected means horizontally or vertically adjacent. BFS (Breadth-First Search) and DFS (Depth-First Search) are two ways to explore these connected groups to count them.

Why it matters

This problem helps us understand how to explore connected parts of data, which is common in maps, networks, and puzzles. Without this, computers would struggle to find groups or clusters in data, making tasks like image recognition or network analysis much harder.

Where it fits

Before this, you should know what grids and basic loops are. After this, you can learn more complex graph algorithms and explore shortest path or cycle detection problems.

Mental Model

Core Idea

To count islands, explore each land cell and mark all connected land cells as visited using BFS or DFS, so you count each island exactly once.

Think of it like...

Imagine a map with lakes and islands. You walk on land and mark every connected piece you can reach without stepping into water. Each time you find new land you haven't visited, that's a new island.

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

Islands found:

  Island 1: top-left cluster (cells with 1s connected)
  Island 2: middle-right cluster
  Island 3: bottom-left single cell
  Island 4: bottom-middle single cell
  Island 5: bottom-right single cell

Build-Up - 7 Steps

1

Foundation

Understanding the grid and islands

Concept: Learn what the grid looks like and what counts as an island.

A grid is a 2D array where each cell is either '1' (land) or '0' (water). Islands are groups of '1's connected horizontally or vertically. Diagonal connections do not count. Your task is to count how many such groups exist.

Result

You can identify separate clusters of '1's visually as islands.

Understanding the problem setup is crucial before applying any search technique.

2

Foundation

Marking visited cells to avoid repeats

Concept: Learn why and how to mark cells so you don't count the same island multiple times.

When you find a land cell, you need to explore all connected land cells. To avoid counting them again, mark them as visited by changing their value or using a separate structure. This prevents infinite loops and double counting.

Result

Each island's cells are visited once and marked, so counting is accurate.

Marking visited cells is the key to correctly counting islands without repetition.

3

Intermediate

Depth-First Search (DFS) exploration

🤔Before reading on: Do you think DFS explores neighbors by going deep first or wide first? Commit to your answer.

Concept: Use DFS to explore all connected land cells by going as deep as possible before backtracking.

Start from a land cell, recursively visit its neighbors (up, down, left, right) if they are land and unvisited. Mark each visited cell. When no more neighbors are left, backtrack. Each DFS call covers one island.

Result

DFS visits all connected land cells of an island, marking them visited.

Knowing DFS explores deeply helps understand how it covers entire islands before moving on.

4

Intermediate

Breadth-First Search (BFS) exploration

🤔Before reading on: Does BFS explore neighbors level by level or go deep first? Commit to your answer.

Concept: Use BFS to explore all connected land cells by visiting neighbors level by level using a queue.

Start from a land cell, add it to a queue. While queue not empty, remove front cell, visit its neighbors (up, down, left, right) if land and unvisited, mark visited and add to queue. BFS covers one island per run.

Result

BFS visits all connected land cells of an island in layers, marking them visited.

Understanding BFS's level-by-level approach helps visualize island coverage differently from DFS.

5

Advanced

Implementing Number of Islands in JavaScript

🤔Before reading on: Will you use DFS or BFS to mark visited cells? Commit to your choice.

Concept: Combine grid traversal with DFS or BFS to count islands in code.

Loop through each cell in the grid. When you find '1', increment island count and run DFS or BFS to mark all connected land cells visited. Continue until all cells checked. Example DFS code snippet: function numIslands(grid) { if (!grid || grid.length === 0) return 0; let count = 0; const rows = grid.length; const cols = grid[0].length; function dfs(r, c) { if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return; grid[r][c] = '0'; // mark visited 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') { count++; dfs(r, c); } } } return count; } Running numIslands on the example grid returns 5.

Result

The function returns the correct number of islands, e.g., 5 for the example grid.

Seeing the full implementation connects theory to practice and shows how BFS/DFS solve the problem.

6

Advanced

Comparing BFS and DFS performance

🤔Before reading on: Do you think BFS or DFS uses more memory on large grids? Commit to your answer.

Concept: Understand the memory and runtime tradeoffs between BFS and DFS in this problem.

DFS uses recursion or a stack, which can go deep and risk stack overflow on large islands. BFS uses a queue and explores neighbors level by level, which can use more memory if many neighbors exist. Both have similar time complexity O(rows*cols), but memory differs based on island shape.

Result

Both BFS and DFS solve the problem correctly, but memory usage varies with grid shape.

Knowing these tradeoffs helps choose the right method for large or complex grids.

7

Expert

Optimizing and handling edge cases

🤔Before reading on: Should you check for empty grids or non-rectangular shapes? Commit to your answer.

Concept: Learn how to handle empty inputs, irregular grids, and optimize marking visited cells.

Check if grid is empty or null before processing. For irregular grids, ensure bounds checks prevent errors. Instead of modifying input grid, use a separate visited matrix if input must stay unchanged. For large grids, iterative DFS avoids stack overflow. Also, consider diagonal connections if problem changes.

Result

Robust code that handles all inputs without crashing and runs efficiently.

Handling edge cases and input constraints is key for production-ready solutions.

Under the Hood

BFS and DFS explore the grid by visiting each land cell once. DFS uses a call stack or explicit stack to go deep into neighbors before backtracking, while BFS uses a queue to visit neighbors level by level. Marking visited cells prevents revisiting and infinite loops. The grid is treated as a graph where each cell is a node connected to up to four neighbors.

Why designed this way?

These methods come from graph theory to explore connected components efficiently. DFS is simple and uses recursion, while BFS is good for shortest path problems. Both avoid repeated work by marking visited nodes. Alternatives like Union-Find exist but BFS/DFS are intuitive and easy to implement.

Grid as graph:

┌───┬───┬───┬───┐
│ 1 │ 1 │ 0 │ 0 │
├───┼───┼───┼───┤
│ 1 │ 1 │ 0 │ 1 │
├───┼───┼───┼───┤
│ 0 │ 0 │ 0 │ 1 │
├───┼───┼───┼───┤
│ 0 │ 0 │ 0 │ 0 │
└───┴───┴───┴───┘

Connections:
(0,0)↔(0,1), (0,0)↔(1,0), (1,0)↔(1,1), etc.

BFS queue or DFS stack explores these connections to mark islands.

Myth Busters - 3 Common Misconceptions

Quick: Does diagonal adjacency count as connected land? Commit yes or no.

Common Belief: Diagonal neighbors are part of the same island.

Reality: Only horizontal and vertical neighbors count as connected land; diagonals do not.

Why it matters: Counting diagonals would merge separate islands incorrectly, giving wrong island counts.

Quick: Can you count islands without marking visited cells? Commit yes or no.

Common Belief: You can count islands by just checking cells without marking visited ones.

Reality: Without marking visited cells, you will count the same island multiple times or get stuck in infinite loops.

Why it matters: Not marking visited cells leads to incorrect counts and inefficient or crashing code.

Quick: Does BFS always use less memory than DFS? Commit yes or no.

Common Belief: BFS always uses less memory than DFS because it explores level by level.

Reality: BFS can use more memory if many neighbors are queued, while DFS uses stack space proportional to depth; memory depends on grid shape.

Why it matters: Assuming BFS always uses less memory can cause unexpected crashes or slowdowns in large or deep grids.

Expert Zone

1

DFS recursion depth can cause stack overflow on very large or skinny islands; iterative DFS avoids this.

2

Modifying the input grid to mark visited cells is memory efficient but destructive; using a separate visited matrix preserves input but uses extra memory.

3

BFS can be optimized by early stopping if only counting islands without full exploration, but this risks missing connected cells.

When NOT to use

For very large grids or when diagonal connections matter, BFS/DFS may be inefficient or incorrect. Alternatives like Union-Find (Disjoint Set Union) can be faster for repeated queries or dynamic grids.

Production Patterns

In real systems, BFS/DFS are used for image segmentation, network cluster detection, and game map analysis. Often combined with memoization or iterative approaches to handle large data efficiently.

Connections

Graph Connected Components

Number of Islands is a special case of finding connected components in a graph.

Understanding connected components in graphs generalizes the island counting problem to many data structures.

Union-Find Data Structure

Union-Find offers an alternative way to group connected land cells without explicit search.

Knowing Union-Find helps optimize island counting when multiple queries or dynamic changes occur.

Epidemiology Spread Models

Exploring connected infected individuals in a population is similar to BFS/DFS island exploration.

Recognizing BFS/DFS patterns in disease spread models shows how algorithms apply beyond computer science.

Common Pitfalls

#1 Not marking visited cells leads to infinite loops or double counting.

Wrong approach:

function dfs(r, c) {
if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return;
// Missing grid[r][c] = '0' to mark visited
dfs(r+1, c);
dfs(r-1, c);
dfs(r, c+1);
dfs(r, c-1);
}

Correct approach:

function dfs(r, c) {
if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return;
grid[r][c] = '0'; // mark visited
dfs(r+1, c);
dfs(r-1, c);
dfs(r, c+1);
dfs(r, c-1);
}

Root cause:

Forgetting to mark visited cells causes repeated visits and infinite recursion.

#2 Counting diagonal neighbors as connected land.

Wrong approach:

function dfs(r, c) {
// Also visit diagonals
dfs(r+1, c+1);
dfs(r+1, c-1);
dfs(r-1, c+1);
dfs(r-1, c-1);
}

Correct approach:

function dfs(r, c) {
dfs(r+1, c);
dfs(r-1, c);
dfs(r, c+1);
dfs(r, c-1);
}

Root cause:

Misunderstanding problem definition about adjacency rules.

#3 Not checking for empty or null grid input.

Wrong approach:

function numIslands(grid) {
// No check for empty grid
let count = 0;
// rest of code
}

Correct approach:

function numIslands(grid) {
if (!grid || grid.length === 0) return 0;
let count = 0;
// rest of code
}

Root cause:

Assuming input is always valid leads to runtime errors.

Key Takeaways

Number of Islands counts connected groups of land cells in a grid using BFS or DFS.

Marking visited cells is essential to avoid counting islands multiple times or infinite loops.

DFS explores deeply before backtracking, while BFS explores neighbors level by level.

Both BFS and DFS have similar time complexity but differ in memory usage depending on grid shape.

Handling edge cases and input validation makes solutions robust and production-ready.

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