[Leetcode] 200. Number of Islands

200. Number of Islands

Given an m x n2D binary grid gridwhich represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

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

Constraints:

m == grid.length

n == grid[i].length

1 <= m, n <= 300

grid[i][j] is '0'or '1'.

How to understand?

the grid has cells which has 1 or 0, 1 is land 0 is water.

when 1 is connected to each other in vertical/horizontal, then it's island.

we don't care about the water, but the important thing is how many island is in the grid.

when we find the first land, we search the layer by layer if it is connected to the other lands in the grid.

How to approach?

BFS, queue

function numIslands(grid: string[][]): number {
    const m = grid.length;
    const n = grid[0].length;

    let count = 0;

    const directions = [
        [1, 0],  // down
        [-1, 0], // up
        [0, 1],  // right
        [0, -1], // left
    ];

    const bfs = (startRow: number, startCol: number) => {
        const queue: [number, number][] = [];
        queue.push([startRow, startCol]);
        grid[startRow][startCol] = '0'; // mark as visited

        while (queue.length > 0) {
            const [r, c] = queue.shift()!;

            for (const [dr, dc] of directions) {
                const nr = r + dr;
                const nc = c + dc;

                if (
                    nr >= 0 && nr < m &&
                    nc >= 0 && nc < n &&
                    grid[nr][nc] === '1'
                ) {
                    queue.push([nr, nc]);
                    grid[nr][nc] = '0'; // mark as visited
                }
            }
        }
    };

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === '1') {
                count++;
                bfs(i, j); // explore the island
            }
        }
    }

    return count;
}

1. set m and n as the row and column of the grid.
2. init count as 0, when we find the new land the count will increment.
3. directions vector for up, down, left, and right direction.
4. double for loop to check the cells in the grid, when it find the first land then increment the count and execute the BFS with the i,j position.
5. BFS takes i and j as row and column position, first create the queue and push the first element of i and j pair.
6. then set the grid's i and j cell as 0, since it's marked so we don't want to care about it.
7. while loop iterate on the queue, check out the first element of the queue and parse is as r and c.
8. create for loop for the 4 directions vector and create neighboured row and column variables.
9. if condition to check the if they are in the bounds and also the cell is "1".
10. when it is, push the neighboured position in queue to check out those neighbour later in while loop and change the neighboured position as 0 in grid.
11. lastly return the count of island in grid.

summary

use queue to check up the layer by layer of neighboured position in grid. mark the visited position as 0. BFS using queue to check the neighboured cells in the grid layer by layer and lastly return the count of the newly found land in the grid.

DFS

class Solution:
    def dfs(self, grid, r, c):
        if (
            r < 0
            or c < 0
            or r >= len(grid)
            or c >= len(grid[0])
            or grid[r][c] != "1"
        ):
            return
        grid[r][c] = "0"

        self.dfs(grid, r - 1, c)
        self.dfs(grid, r + 1, c)
        self.dfs(grid, r, c - 1)
        self.dfs(grid, r, c + 1)

    def numIslands(self, grid):
        if not grid:
            return 0

        num_islands = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    self.dfs(grid, i, j)
                    num_islands += 1

        return num_islands

Similar to BFS approach. but in dfs way.

implement 2 different def in Solution.

create num_islands as 0 to count the total number of islands in the grid.

nested for loop will go through the each island on the grid.

when the island is found then use the coordinates in dfs function.

dfs function will check if the coordinates are in the grid, and if it is island.

when they pass the if condition, then the coordinates value will be replaced as 0.

and recursively call the dfs function as updated coordinates(up,down,left,right)

lastly return the num_islands