Number of Islands

Medium Problem 99 of 151 Java and Python

Practice on LeetCode

Problem

Given an m × n grid of "1" (land) and "0" (water), return the number of islands.

An island is land connected horizontally or vertically and surrounded by water. Everything outside the grid is water.

Example 1

Input: grid = ["11110", "11010", "11000", "00000"]
Output: 1

Example 2

Input: grid = ["11000", "11000", "00100", "00011"]
Output: 3

Constraints

1 ≤ m, n ≤ 300

Explanation

Scan the grid. Each time you find land you have not seen yet, you found a new island: count it, then "sink" the whole island with a DFS or BFS so none of its cells are counted again.

Approach 1 · Better

BFS from each new island

Time O(m · n)
Space O(min(m, n)) queue

When you meet unvisited land, count it and BFS through the whole island, marking cells as water.

For each cell with "1": increment the count, set it to "0", and push it on a queue.
Pop cells, turning neighbouring land to water and enqueuing it.

Java

import java.util.*;

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '1') {
                    continue;
                }
                count++;
                grid[i][j] = '0';
                Deque<int[]> queue = new ArrayDeque<>();
                queue.add(new int[] { i, j });
                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    for (int[] d : dirs) {
                        int r = cell[0] + d[0];
                        int c = cell[1] + d[1];
                        if (r >= 0 && c >= 0 && r < m && c < n && grid[r][c] == '1') {
                            grid[r][c] = '0';
                            queue.add(new int[] { r, c });
                        }
                    }
                }
            }
        }
        return count;
    }
}

Python

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] != "1":
                    continue
                count += 1
                grid[i][j] = "0"
                queue = deque([(i, j)])
                while queue:
                    r, c = queue.popleft()
                    for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "1":
                            grid[nr][nc] = "0"
                            queue.append((nr, nc))
        return count

Approach 2 · Optimal

DFS that sinks each island

Time O(m · n)
Space O(m · n) recursion worst case

Same counting idea, with a short recursive DFS that turns the island to water.

For each "1": increment the count and call sink(i, j).
sink: stop at bounds or water; otherwise set "0" and recurse in four directions.

Java

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

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

Python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])

        def sink(r, c):
            if not (0 <= r < m and 0 <= c < n) or 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)

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

Complexity compared

Approach	Time	Space
Better BFS from each new island	O(m · n)	O(min(m, n)) queue
Optimal DFS that sinks each island	O(m · n)	O(m · n) recursion worst case

Key takeaways

"Count connected groups" = number of times you start a new DFS/BFS. Union-Find is the third standard answer.
Modifying the grid saves a visited array; mention it if the input must not change.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem