Number of Islands | DFS vs BFS

🌊 The Problem

We have a 2D map grid filled with '1's land and '0's water. An island is a group of connected '1's (horizontally or vertically). Our mission? Count how many islands exist!

Example 1:

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

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

🔍 Two Explorers, One Mission

We can solve this with DFS (Depth-First Search) or BFS (Breadth-First Search). Let’s see how they differ

💡 Key Takeaways

1. DFS = I found land! Let me explore all connected land immediately!
2. BFS = I found land! Let me first note all neighbors, then explore them one by one.
3. Both mark visited land to avoid double-counting.

var numIslands = function(grid) {
    let count = 0
    for(let i = 0; i < grid.length; i++){
        for(let j = 0; j < grid[0].length; j++){
            if(grid [i][j] === '1'){
                    count++
                    dfs(i, j, grid)
            }
        }
    }
    return count
};

function inBound(min, value, max){
    return min < value && value < max
}

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

function dfs(row, col, grid){
    if(!inBound(-1, row, grid.length)
        || !inBound(-1, col, grid[0].length)
        || grid[row][col] ==='0'
    ){
        return
    }
     grid[row][col] ='0' 

    for (let [dirRow, dirCol] of directions){
        const newRow = row + dirRow
        const newCol = col + dirCol
        dfs(newRow, newCol, grid)
    }
}

bfs(grid, startRow, startCol) {
        const queue = []
        queue.push([startRow, startCol])

        while (0 < queue.length) {
            const [row, col] = queue.shift()

            for (const [dirRow, dirCol] of this.directions) {
                const newRow = dirRow + row
                const newCol = dirCol + col

                if (
                    this.inBound(-1, newRow, grid.length)
                    && this.inBound(-1, newCol, grid[0].length)
                    && grid[newRow][newCol] === '1'
                ) {
                    grid[newRow][newCol] = '0'
                    queue.push([newRow, newCol])
                }
            }
        }
    }

It's like:

• DFS: "I'm here, let me check if I'm valid"
• BFS: "Let me check if my neighbor is valid before I go there"