Number of Islands

Published at25 Jul 2026

Graph DFS Medium 0 views

Like0

You are given a 2D grid containing '1' (land) and '0' (water). Count the number of islands. An island is formed by connecting adjacent land cells horizontally or vertically (not diagonally). All four edges of the grid are surrounded by water.

Use Depth-First Search (DFS) to explore each island. Iterate through every cell in the grid. When a '1' is found, increment the island counter and perform DFS to mark all connected land cells as visited by changing them to '0'. This process ensures each island is counted exactly once.

The DFS function checks boundary conditions and returns if the cell is out of bounds or is water. It marks the current cell as visited (changes '1' to '0') and recursively explores all four adjacent directions: up, down, left, and right.

Time complexity is O(m * n) where m and n are the grid dimensions, since each cell is visited at most once. Space complexity is O(m * n) in the worst case for the recursion stack when the entire grid is land. This approach is efficient and avoids revisiting cells.

Edge cases include empty grid, grid with no land (return 0), single cell grid, and grid where islands touch the boundary. The algorithm correctly handles all cases by systematically exploring connected components.

Example Input & Output

Example 1

Input

[["1"]]

Output

Explanation

Single cell island

Example 2

Input

[[],[],[]]

Output

Explanation

Empty rows

Example 3

Input

[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]

Output

Explanation

Three separate islands

Example 4

Input

[["0"]]

Output

Explanation

No island

Example 5

Input

[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]

Output

Explanation

All 1s form one island

Algorithm Flow

Recommendation Algorithm Flow for Number of Islands

Solution Approach

Count the number of islands in a 2D grid where '1' is land and '0' is water. Islands are groups of adjacent land cells connected horizontally or vertically. Use DFS: iterate through every cell. When land is found, increment the count and recursively sink the entire island by marking visited cells as '0'. Each cell is visited once.

function numIslands(grid) {
  var count = 0;
  for (var r = 0; r < grid.length; r++) {
    for (var c = 0; c < grid[r].length; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
  function dfs(r, c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[r].length || grid[r][c] === '0') return;
    grid[r][c] = '0';
    dfs(r - 1, c); dfs(r + 1, c); dfs(r, c - 1); dfs(r, c + 1);
  }
}

Modifying the grid to mark visited cells avoids allocating a separate visited array. The DFS explores all four directions recursively, covering the entire island.

Time complexity is O(rows * cols), space complexity is O(rows * cols) for the recursion stack.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

class Solution {
    int rows, cols;
    public int solution(String[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        rows = grid.length; cols = grid[0].length;
        int count = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j].equals("1")) { count++; dfs(grid, i, j); }
            }
        }
        return count;
    }
    void dfs(String[][] g, int i, int j) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || g[i][j].equals("0")) return;
        g[i][j] = "0";
        dfs(g, i-1, j); dfs(g, i+1, j); dfs(g, i, j-1); dfs(g, i, j+1);
    }
}

javascript

function solution(grid) {
  if (!grid || grid.length === 0 || !grid[0]) return 0;
  var rows = grid.length, cols = grid[0].length, count = 0;
  function dfs(i, j) {
    if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] === '0') return;
    grid[i][j] = '0';
    dfs(i-1, j); dfs(i+1, j); dfs(i, j-1); dfs(i, j+1);
  }
  for (var i = 0; i < rows; i++) {
    for (var j = 0; j < cols; j++) {
      if (grid[i][j] === '1') { count++; dfs(i, j); }
    }
  }
  return count;
}

php

<?php
function solution($grid) {
    if (empty($grid) || empty($grid[0])) return 0;
    $rows = count($grid); $cols = count($grid[0]); $count = 0;
    $dfs = function(&$g, $i, $j) use (&$dfs, $rows, $cols) {
        if ($i < 0 || $i >= $rows || $j < 0 || $j >= $cols || $g[$i][$j] === '0') return;
        $g[$i][$j] = '0';
        $dfs($g, $i-1, $j); $dfs($g, $i+1, $j); $dfs($g, $i, $j-1); $dfs($g, $i, $j+1);
    };
    for ($i = 0; $i < $rows; $i++) {
        for ($j = 0; $j < $cols; $j++) {
            if ($grid[$i][$j] === '1') { $count++; $dfs($grid, $i, $j); }
        }
    }
    return $count;
}

python

def solution(grid):
    if not grid or not grid[0]: return 0
    rows, cols = len(grid), len(grid[0])
    def dfs(i, j):
        if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] == '0':
            return
        grid[i][j] = '0'
        dfs(i-1, j); dfs(i+1, j); dfs(i, j-1); dfs(i, j+1)
    count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    return count

rust

fn solution(grid: Vec<Vec<String>>) -> i32 {
    if grid.is_empty() || grid[0].is_empty() { return 0; }
    let rows = grid.len(); let cols = grid[0].len();
    let mut g = grid; let mut count = 0i32;
    for i in 0..rows {
        for j in 0..cols {
            if g[i][j] == "1" { count += 1; dfs(&mut g, i as i32, j as i32, rows as i32, cols as i32); }
        }
    }
    count
}
fn dfs(g: &mut Vec<Vec<String>>, i: i32, j: i32, rows: i32, cols: i32) {
    if i < 0 || i >= rows || j < 0 || j >= cols || g[i as usize][j as usize] == "0" { return; }
    g[i as usize][j as usize] = "0".to_string();
    dfs(g, i-1, j, rows, cols); dfs(g, i+1, j, rows, cols);
    dfs(g, i, j-1, rows, cols); dfs(g, i, j+1, rows, cols);
}

typescript

function solution(grid: string[][]): number {
    if (!grid || grid.length === 0 || !grid[0]) return 0;
    var rows = grid.length, cols = grid[0].length, count = 0;
    function dfs(i: number, j: number): void {
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] === '0') return;
        grid[i][j] = '0';
        dfs(i-1, j); dfs(i+1, j); dfs(i, j-1); dfs(i, j+1);
    }
    for (var i = 0; i < rows; i++) {
        for (var j = 0; j < cols; j++) {
            if (grid[i][j] === '1') { count++; dfs(i, j); }
        }
    }
    return count;
}

Related Graph Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Number of Islands

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Graph Challenges

Garden Relay Count

Catalog Shelf Lineup

Ascending Manifest

Mountain Cabin Signal Range

Seaport Ferry Gate Control

City Bus Loop Access

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.