Coding problem · Medium · Graphs

Number of Islands

Medium Algorithms & data structures Most askedSeen at Amazon, Google, Meta, Microsoft, Bloomberg

Given an m × n grid of 1 (land) and 0 (water), return the number of islands. An island is a group of land cells connected horizontally or vertically.

Example 1

Input: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]
Output: 3

Hints

Hint 1

Scan every cell; when you find unvisited land, count an island and flood-fill (DFS/BFS) to mark all of it visited.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(m·n) · Space O(m·n) worst-case recursion/queue

Each time the scan meets unvisited land, increment the count and sink the whole island (set cells to 0) with DFS or BFS so it's not counted again. Every cell is processed a constant number of times.

Reference solution

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

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

def num_islands(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])

    def sink(r: int, c: int) -> None:
        stack = [(r, c)]
        grid[r][c] = 0
        while stack:
            y, x = stack.pop()
            for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
                if 0 <= ny < m and 0 <= nx < n and grid[ny][nx] == 1:
                    grid[ny][nx] = 0
                    stack.append((ny, nx))

    count = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:
                count += 1
                sink(r, c)
    return count

<?php

function numIslands(array $grid): int
{
    $m = count($grid);
    $n = count($grid[0]);
    $count = 0;
    for ($r = 0; $r < $m; $r++) {
        for ($c = 0; $c < $n; $c++) {
            if ($grid[$r][$c] !== 1) {
                continue;
            }
            $count++;
            $stack = [[$r, $c]];
            $grid[$r][$c] = 0;
            while ($stack) {
                [$y, $x] = array_pop($stack);
                foreach ([[1, 0], [-1, 0], [0, 1], [0, -1]] as [$dy, $dx]) {
                    [$ny, $nx] = [$y + $dy, $x + $dx];
                    if ($ny >= 0 && $nx >= 0 && $ny < $m && $nx < $n && $grid[$ny][$nx] === 1) {
                        $grid[$ny][$nx] = 0;
                        $stack[] = [$ny, $nx];
                    }
                }
            }
        }
    }
    return $count;
}

class Solution {
    public int numIslands(int[][] grid) {
        int count = 0;
        for (int r = 0; r < grid.length; r++)
            for (int c = 0; c < grid[0].length; c++)
                if (grid[r][c] == 1) { count++; sink(grid, r, c); }
        return count;
    }

    private void sink(int[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != 1) return;
        g[r][c] = 0;
        sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1);
    }
}

Common mistakes

Counting diagonal neighbours (only 4 directions).
Deep recursion on huge all-land grids — mention BFS or an explicit stack.

Course Schedule · Medium
Find Deadlocked Transactions · Medium