Number of Islands

Problem

Given an m x n 2D binary grid grid which 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'.

Solution

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let islands = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === "1") { // if is land (ie. not visited and not water)
                islands++;
                dfs(grid, i, j);
            }
        }
    }
    return islands;
};

var dfs = function(grid, row, col) {
    // (row, rol) is not out of range, has not been visited, and is land
    if (grid?.[row]?.[col] === "1") {
        grid[row][col] = null;
        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col + 1);
        dfs(grid, row, col - 1);
    }
};

We will implement a DFS solution. We iterate through grid and apply DFS method dfs at (i, j) if it is land and has not been visited yet (use null to denote visited). More specifically, dfs will traverse the entire island and mark all parts of the island as being visited. This means when we iterate through grid in the numIslands method, if (row, col) is land and has not been visited yet, it must be a new island.

Problem​

Solution​

Problem

Solution