Number of Islands Medium 0 attempts
Daily GeeksforGeeks ↗

Number of Islands

Medium MatrixBFSDFS GeeksforGeeks

You're given a 2D grid of size m x n made up of '1's (land) and '0's (water), fully surrounded by water on all sides. An island is a group of land cells connected horizontally or vertically — diagonal connections don't count. Count how many separate islands the grid contains.

Input Format
Implement numIslands(grid). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
grid = [["0"]]
Output
0
Constraints
  • 1 <= m, n <= 300
  • grid[i][j] is '1' or '0'
Test Cases (2)
Case 1
Args: [[["1","1","0"],["0","1","0"],["0","0","1"]]] Expected: 2
Case 2
Args: [[["0"]]] Expected: 0
Topics
MatrixBFSDFS

Iterative Flood Fill

Each unvisited land cell starts a new island. Mark cells when they enter the stack so every land cell is processed once.

javascript
function numIslands(grid) {
  const rows=grid.length,cols=grid[0].length;let count=0;
  for(let r=0;r<rows;r++)for(let c=0;c<cols;c++) {
    if(grid[r][c]!=='1')continue;
    count++;grid[r][c]='0';const stack=[[r,c]];
    while(stack.length){const [x,y]=stack.pop();for(const [dx,dy] of [[1,0],[-1,0],[0,1],[0,-1]]){
      const nx=x+dx,ny=y+dy;
      if(nx>=0&&nx<rows&&ny>=0&&ny<cols&&grid[nx][ny]==='1'){grid[nx][ny]='0';stack.push([nx,ny]);}
    }}
  }
  return count;
}

Time: O(rows × cols) | Space: O(rows × cols)

Saved in this browser only. Private to you.

JavaScript