Course4all
Join us on telegram
Home/dsa/Graphs/Number of Islands

Number of Islands

Master this topic with zero to advance depth.

Number of Islands

Given an m x 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 all surrounded by water.

Visual Representation

Grid: 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 Islands: 3 (Top-left, Middle, Bottom-right)
Medium

Examples

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

Three distinct connected groups of '1's.

Approach 1

Level II: Intermediate (Union-Find)

Intuition

Each land cell '1' can be seen as a node. Adjacent '1's belong to the same connected component. We can use the Disjoint Set Union (DSU) to group these cells and count the number of resulting sets.

Thought Process

  1. Count total '1's in the grid (initial component count).
  2. Iterate through every cell. If it's a '1', check its Right and Down neighbors.
  3. If a neighbor is also '1', perform a union. If they were in different sets, decrement the component count.
  4. Return the final count of components.

Pattern: Disjoint Set Union (DSU)

⏱ O(M * N * alpha(MN)) - alpha is the inverse Ackermann function.💾 O(M * N) - For the parent array in DSU.

Detailed Dry Run

Grid: [[1,1], [0,1]]

CellNeighborsActionSets
(0,0)(0,1) is '1'Union(0,1){0,1}, {1,1} (Count: 2)
(0,1)(1,1) is '1'Union(1,1){0,1,1,1} (Count: 1)
Result: 1
java
class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length, cols = grid[0].length;
        DSU dsu = new DSU(grid);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    if (r + 1 < rows && grid[r + 1][c] == '1') dsu.union(r * cols + c, (r + 1) * cols + c);
                    if (c + 1 < cols && grid[r][c + 1] == '1') dsu.union(r * cols + c, r * cols + (c + 1));
                }
            }
        }
        return dsu.count;
    }
    class DSU {
        int[] parent; int count;
        DSU(char[][] grid) {
            int m = grid.length, n = grid[0].length;
            parent = new int[m * n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        count++;
                    }
                }
            }
        }
        int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); }
        void union(int i, int j) {
            int rootI = find(i), rootJ = find(j);
            if (rootI != rootJ) { parent[rootI] = rootJ; count--; }
        }
    }
}
Approach 2

Level III: Optimal (DFS / BFS)

Intuition

Each cell '1' is a node, and adjacent '1's have edges. We can use a traversal to find Connected Components. When we find a '1', we launch a DFS/BFS to visit all reachable '1's and mark them as '0' ("sinking" the island) to avoid re-visiting.

Thought Process

  1. Iterate through every cell (r, c).
  2. If grid[r][c] == '1':
    • Increment count.
    • Launch DFS starting from (r, c).
  3. In DFS:
    • Reached Water or Out of Bounds? Return.
    • Mark current cell as '0' (visited).
    • Recurse in 4 directions.

Pattern: Connected Components / Flood Fill

⏱ O(M * N) - Each cell is visited constant number of times.💾 O(M * N) - Recursion stack in the worst case (all land).

Detailed Dry Run

Grid: [[1,1], [0,1]]

i, jValActionCount
0,0'1'Start DFS. Sink (0,0), (0,1), (1,1)1
0,1'0'Skip1
1,1'0'Skip1
Final Count: 1
java
public 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++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0') return;
        grid[r][c] = '0'; // Sink it
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
}
← Previous QuestionCourse Schedule
Next Question →Clone Graph