Number of Islands BFS and DFS in DSA Typescript - 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 of water and land. Each cell can be either land or water, and connected land cells form an island. We use BFS (Breadth-First Search) or DFS (Depth-First Search) to explore and count these islands. This helps understand how to traverse grids and group connected components.

Why it matters

Without this concept, we couldn't easily find connected areas in maps or grids, which is important in many real-world tasks like finding clusters in images, analyzing networks, or mapping regions. It teaches how to explore neighbors systematically and avoid counting the same area multiple times. This skill is foundational for many problems involving grids and graphs.

Where it fits

Before this, you should know basic arrays and loops. After this, you can learn graph traversal algorithms more deeply, like shortest path or cycle detection. This topic builds a bridge from simple loops to exploring complex structures like graphs.

Mental Model

Core Idea

Explore each land cell and mark all connected land cells as visited to count one island, repeating until all land is counted.

Think of it like...

Imagine walking through a forest where each tree is a land cell. When you find a tree, you walk around to find all trees connected to it without stepping into water. Once you finish, you know one forest area. Then you look for another tree not visited yet to find the next forest.

Grid example:
  1 1 0 0 0
  1 1 0 0 1
  0 0 0 1 1
  0 0 0 0 0
  1 0 0 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-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). An island is a group of '1's connected horizontally or vertically (not diagonally). Your task is to count how many such islands exist.

Result

You can identify separate groups of connected '1's as islands.

Understanding the problem setup is key before trying to solve it; knowing what counts as connected land helps guide the search.

2

Foundation

Marking visited cells to avoid repeats

Concept: Learn to track which cells have been checked to avoid counting the same island multiple times.

When you find a land cell, you need to mark it as visited so you don't count it again. This can be done by changing its value or using a separate visited array. This prevents infinite loops and double counting.

Result

You can safely explore the grid without revisiting the same land cells.

Tracking visited cells is essential to correctly count islands and avoid infinite loops during traversal.

3

Intermediate

Depth-First Search (DFS) traversal

🤔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 starting from one cell by going as deep as possible before backtracking.

Starting from a land cell, recursively visit its neighbors (up, down, left, right) if they are land and not visited. Mark each visited cell. When no more neighbors are left, one island is fully explored.

Result

All connected land cells of one island are marked visited after DFS completes.

Understanding DFS helps you explore connected components deeply, which is efficient for this problem.

4

Intermediate

Breadth-First Search (BFS) traversal

🤔Before reading on: do you think BFS explores neighbors level by level or goes deep first? Commit to your answer.

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

Starting from a land cell, add it to a queue. While the queue is not empty, remove a cell, mark it visited, and add all unvisited land neighbors to the queue. This continues until the queue is empty, meaning the island is fully explored.

Result

All connected land cells of one island are marked visited after BFS completes.

Knowing BFS allows you to explore neighbors in layers, which can be easier to implement iteratively.

5

Intermediate

Counting islands by scanning the grid

🤔Before reading on: do you think counting islands requires scanning every cell or just some? Commit to your answer.

Concept: Scan every cell in the grid. When you find an unvisited land cell, start DFS or BFS to mark the whole island visited and increment the island count.

Loop through each cell. If it's land and not visited, run DFS/BFS from there. Each such run counts as one island. Continue until all cells are checked.

Result

You get the total number of islands in the grid.

Systematically scanning ensures no island is missed and counting is accurate.

6

Advanced

Optimizing space by modifying the grid

🤔Before reading on: do you think using a separate visited array is necessary or can the grid be reused? Commit to your answer.

Concept: Instead of using extra space for visited cells, modify the grid in place to mark visited land cells by changing '1' to '0'.

When visiting a land cell, change its value to '0' to mark it visited. This saves memory but changes the input grid.

Result

The grid itself tracks visited cells, reducing space usage.

Knowing in-place modification can save memory is important for large grids or memory-limited environments.

7

Expert

Handling edge cases and large grids efficiently

🤔Before reading on: do you think recursion depth or queue size can cause problems in large grids? Commit to your answer.

Concept: Understand limitations like recursion stack overflow in DFS and memory usage in BFS, and how to handle them.

In very large grids, recursive DFS may cause stack overflow. Iterative DFS using a stack or BFS with a queue is safer. Also, consider early stopping if needed and efficient neighbor checks.

Result

Your solution works reliably on large inputs without crashing.

Knowing practical limits and how to avoid them is key for production-ready code.

Under the Hood

The algorithm treats the grid as a graph where each cell is a node connected to its adjacent nodes (up, down, left, right). BFS and DFS traverse this graph to find connected components (islands). Visited tracking prevents revisiting nodes, ensuring each island is counted once. BFS uses a queue to explore neighbors level by level, while DFS uses recursion or a stack to explore deeply before backtracking.

Why designed this way?

This approach leverages classic graph traversal methods adapted to grids, which are simpler to represent and traverse. Using BFS or DFS ensures all connected nodes are found efficiently. Alternatives like union-find exist but are more complex to implement for beginners. Marking visited cells prevents infinite loops and double counting, a common problem in naive approaches.

Grid as graph:
┌───┬───┬───┐
│ 1 │ 1 │ 0 │
├───┼───┼───┤
│ 0 │ 1 │ 0 │
├───┼───┼───┤
│ 0 │ 0 │ 1 │
└───┴───┴───┘

Connections:
(0,0)─(0,1)
  │      │
(1,1)    

Traversal:
Start at (0,0), visit (0,1), then (1,1), marking visited.
Each visited node is removed from queue/stack until island fully explored.

Myth Busters - 4 Common Misconceptions

Quick: Does diagonal adjacency count as connected land in this problem? Commit to yes or no.

Common Belief: Many think diagonally touching land cells form one island.

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

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

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

Common Belief: Some believe you can just count land cells without tracking visits.

Reality: Without marking visited, you will count the same island multiple times, inflating the count.

Why it matters: This leads to incorrect island counts and infinite loops during traversal.

Quick: Is BFS always better than DFS for this problem? Commit to yes or no.

Common Belief: Some think BFS is always faster or better than DFS here.

Reality: Both BFS and DFS have similar time complexity; choice depends on implementation and constraints.

Why it matters: Choosing BFS over DFS without reason may cause stack overflow or memory issues in large grids.

Quick: Does modifying the input grid to mark visited cells always cause problems? Commit to yes or no.

Common Belief: Many think changing the input grid is always bad and should be avoided.

Reality: Modifying the grid is a common and efficient practice if input preservation is not required.

Why it matters: Avoiding grid modification unnecessarily uses extra memory, which can be costly in large inputs.

Expert Zone

1

DFS recursion depth can cause stack overflow; iterative DFS with an explicit stack avoids this.

2

BFS queue size can grow large in dense islands, impacting memory; sometimes DFS is more memory efficient.

3

In-place grid modification is a tradeoff: saves memory but destroys input; cloning grid is safer but costly.

When NOT to use

For very large grids or real-time systems, union-find (disjoint set) data structures may be better for dynamic connectivity queries. Also, if diagonal connections matter, this approach must be adapted or replaced.

Production Patterns

In real systems, this pattern is used in image processing to find connected pixels, in geographic information systems to find land masses, and in network analysis to find connected components. Implementations often use iterative DFS or BFS with in-place marking for efficiency.

Connections

Graph Connected Components

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

Understanding this problem helps grasp how to find groups of connected nodes in any graph.

Flood Fill Algorithm

Flood fill uses similar traversal to fill connected areas, like painting connected pixels.

Knowing Number of Islands traversal clarifies how flood fill spreads through connected regions.

Epidemiology Spread Models

The way BFS/DFS explores connected cells is similar to how diseases spread through connected populations.

Understanding traversal helps model and predict spread patterns in real-world networks.

Common Pitfalls

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

Wrong approach:

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

// No marking visited

Correct approach:

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

Root cause:

Forgetting to mark visited cells means the algorithm revisits the same cells endlessly or counts islands multiple times.

#2 Counting diagonal neighbors as connected land.

Wrong approach:

function dfs(grid, r, c) {
// checks up, down, left, right, AND diagonals
// e.g., r+1,c+1 or r-1,c-1 included
}

Correct approach:

function dfs(grid, r, c) {
// only check r+1,c; r-1,c; r,c+1; r,c-1
}

Root cause:

Misunderstanding problem definition leads to incorrect neighbor checks.

#3 Using recursive DFS on very large grids causing stack overflow.

Wrong approach:

function dfs(grid, r, c) {
if (invalid) 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);
}
// Called on large grid

Correct approach:

function iterativeDFS(grid, r, c) {
const stack = [[r, c]];
while (stack.length) {
const [x, y] = stack.pop();
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] === '0') continue;
grid[x][y] = '0';
stack.push([x+1, y], [x-1, y], [x, y+1], [x, y-1]);
}
}

Root cause:

Not considering recursion limits causes crashes on large inputs.

Key Takeaways

Number of Islands counts connected groups of land cells in a grid using graph traversal.

Marking visited cells is essential to avoid double counting and infinite loops.

DFS explores deeply using recursion or stack, while BFS explores neighbors level by level using a queue.

Modifying the grid in place can save memory but changes the input data.

Handling large grids requires iterative traversal to avoid stack overflow and careful memory management.