Number of Islands

Problem Description

Given an m × n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Examples

Constraints

• m == grid.length
• n == grid[i].length
• 1 ≤ m, n ≤ 300
• grid[i][j] is '0' or '1'.

Sinking Discovered Land to Count Disjoint Components

This problem asks us to find the number of connected components in a grid graph. Every '1' is a node, and adjacent '1's share an edge.

We can scan the grid cell by cell. When we find a '1', it means we have discovered a new island. We increment our island counter. We then run a Depth-First Search (DFS) starting from that cell to find and visit all connected land cells belonging to the same island.

To avoid counting the same island multiple times, we must mark visited cells. We can do this without extra memory by “sinking” the island: setting grid[r][c] = '0' for all visited land cells during the DFS. Once the DFS completes, we continue our scan. Any new '1' we find must belong to a separate, disjoint island.

Solution 1: DFS Grid Sinking (In-Place)

Scan the grid and run a recursive DFS to clear adjacent land nodes when an island is encountered.

class Solution {
    public int numIslands(char[][] 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++;
                    dfs(grid, r, c); // sink the island
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int r, int c) {
        // check boundaries and water cells
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0'; // sink the land

        // visit adjacent cells
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
}

class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])
        count = 0

        def dfs(r, c):
            # check boundaries and water cells
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == "0":
                return

            grid[r][c] = "0"  # sink the land

            # visit adjacent cells
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":
                    count += 1
                    dfs(r, c)  # sink the island

        return count

#include <vector>

class Solution {
private:
    void dfs(std::vector<std::vector<char>>& grid, int r, int c) {
        // check boundaries and water cells
        if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0'; // sink the land

        // visit adjacent cells
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }

public:
    int numIslands(std::vector<std::vector<char>>& grid) {
        int count = 0;
        for (int r = 0; r < grid.size(); r++) {
            for (int c = 0; c < grid[0].size(); c++) {
                if (grid[r][c] == '1') {
                    count++;
                    dfs(grid, r, c); // sink the island
                }
            }
        }
        return count;
    }
};

Complexity Analysis:

• Time Complexity: O(M * N) where M is the number of rows and N is the number of columns. We visit each grid cell at most once.
• Space Complexity: O(M * N) in the worst case (the entire grid is land), representing the recursion stack depth.

Where it breaks: This in-place modification mutates the input array. If mutating the input is not allowed, you must use a separate visited boolean grid, which increases auxiliary space to O(M * N).

Common Mistakes

• Not checking boundaries before indexing. You must verify coordinate bounds before accessing grid[r][c] to avoid crashes.
• Incorrectly processing diagonals. The problem states that islands are formed by connecting adjacent lands horizontally or vertically. Do not include diagonal checks.
• Using integer 0 instead of char ‘0’. The grid consists of character arrays, so the checks must evaluate '0' and '1', not numeric 0 and 1.

Frequently Asked Questions

Can we solve this using Breadth-First Search (BFS)? Yes. You can use a queue instead of recursion. When a '1' is found, push its coordinates to a queue, sink it, and then iteratively pop, push neighbors, and sink them until the queue is empty. This avoids recursion stack frames.

Can we use Union-Find for this problem? Yes. You can treat each land cell as a disjoint set and union them with their neighbors. The final number of islands is the number of distinct parent pointers pointing to land cells. This has a slightly higher overhead but is useful for dynamic, streaming grid modifications.

What does this problem test in interviews? It tests your ability to run traversals on 2D grids, manage recursion base cases, and identify connected components in implicit graphs.

← All Problems