Leetcode - 200. Number of Islands

🔍 Approach: BFS

We traverse each cell in the grid. When we encounter a land cell ("1") that we haven’t visited, we perform a BFS from that cell, marking all connected land cells as visited. Every BFS call corresponds to discovering a new island.

We use a Set to keep track of visited cells and a queue for BFS traversal. For each land cell, we explore its 4-connected neighbors (up, down, left, right).

---

🧠 Why BFS?

• It systematically explores all neighbors level by level.
• Easy to implement with a queue.
• Perfect fit when you need to cover all connected components from a starting point.

---

🧪 Code (Using BFS)

/**
 * @param {character[][]} grid
 * @return {number}
 */

var numIslands = function (grid) {
    let visited = new Set();
    let islands = 0;

    //bfs method
    function bfs(r, c) {
        let queue = [];
        visited.add(JSON.stringify([r, c]));
        queue.push([r, c]);
        while (queue.length > 0) {
            let [row, col] = queue.shift();
            //visit the neighbors
            let directions = [
                [1, 0],
                [-1, 0],
                [0, 1],
                [0, -1],
            ];
            for (let [dr, dc] of directions) {
                const newRow = row + dr;
                const newCol = col + dc;

                if (newRow >= 0 && newRow < grid.length && //ensuring to not go out of grid bounds
                    newCol >= 0 && newCol < grid[0].length && //ensuring to not go out of grid bounds
                    !visited.has(JSON.stringify([newRow, newCol])) && grid[newRow][newCol] === "1") {
                    visited.add(JSON.stringify([newRow, newCol]));
                    queue.push([newRow, newCol]);
                }
            }
        }
    }

    //base case (if grid is null , return 0 islands)
    if (!grid) return 0;
    // we need to traverse in a bfs manner to cover the island paths

    //traverse through the grid  
    const cols = grid[0].length; 
    const rows = grid.length; 

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            // here we need to do bfs for the elements which are island and not yet visited;
            if (grid[i][j] === "1" && !visited.has(JSON.stringify([i, j]))) {
                bfs(i, j);
                islands++; // we come here once bfs is ended ie we reached end of one island
            }
        }
    }
    return islands;
};

---

⏱️ Time and Space Complexity

⏳ Time Complexity: O(m * n)

• Every cell is visited once.
• For each land cell, we explore all its neighbors.
• Total operations scale linearly with the number of cells.

💾 Space Complexity: O(m * n)

• In the worst case (all land), the visited set and BFS queue can grow to the size of the entire grid.

Where m is the number of rows and n is the number of columns.

---

✅ Example

Input:

[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Output:

3

Each cluster of '1's represents an island. Diagonal connections are not considered.

---

🧭 Summary

• Traverse the grid.
• For each unvisited land cell, start a BFS and mark all connected land as visited.
• Count how many times you start BFS — that's your number of islands!

---