Number of Islands | Problems

Given a grid, count the number of islands. An island is formed by connecting adjacent lands horizontally or vertically.

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

Sample Input

—

Sample Output

—

Constraints

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

Topics

Graph 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.