Number of Islands | Problems

Given an m×n 2D grid of '1's (land) and '0's (water), count the number of islands.

Example: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]] → Output: 3

Sample Input

—

Sample Output

—

Constraints

1 <= m, n <= 300
grid[i][j] is '1' or '0'

Topics

Matrix BFS DFS

DFS Flood Fill

function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== '1') return;
    grid[r][c] = '0';
    dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
  }
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      if (grid[i][j] === '1') { count++; dfs(i, j); }
  return count;
}

Time: O(mn) | Space: O(mn)

Saved in this browser only. Private to you.