Course4all
Join us on telegram
Home/dsa/Union Find/Number of Islands

Number of Islands

Master this topic with zero to advance depth.

Number of Islands

Given an m×nm \times n 2D binary grid, return the number of islands. An island is surrounded by water and is formed by connecting adjacent land cells horizontally or vertically.

Medium

Examples

Input: grid = [["1","1","0"],["1","1","0"],["0","0","1"]]
Output: 2
Approach 1

Level I: DFS (Matrix Traversal)

Intuition

Traverse the grid. When we find '1' (land), increment the island count and use DFS to mark all connected land as '0' (visited).

⏱ O(M \cdot N)💾 O(M \cdot N)

Detailed Dry Run

Found '1' at (0,0). Increment count. DFS marks (0,1), (1,0), (1,1) as '0'. Continue.

java
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); }
            }
        }
        return count;
    }
    private void dfs(char[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] == '0') return;
        g[r][c] = '0';
        dfs(g, r+1, c); dfs(g, r-1, c); dfs(g, r, c+1); dfs(g, r, c-1);
    }
}
Approach 2

Level III: Union-Find (Grid Logic)

Intuition

Treat each land cell as a node in a DSU. For every '1', union it with its neighbors. The number of islands is the number of land cells minus successful unions.

⏱ O(M \cdot N \cdot \alpha(M \cdot N))💾 O(M \cdot N)

Detailed Dry Run

Total '1's = 5. Union (0,0) and (0,1) -> success, count becomes 4. Union (0,0) and (1,0) -> success, count becomes 3.

java
class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] p = new int[m*n]; int count = 0;
        for(int i=0; i<m; i++) for(int j=0; j<n; j++) if(grid[i][j]=='1') { p[i*n+j]=i*n+j; count++; }
        for(int i=0; i<m; i++) for(int j=0; j<n; j++) if(grid[i][j]=='1') {
            if(i+1<m && grid[i+1][j]=='1') { int r1=find(p, i*n+j), r2=find(p, (i+1)*n+j); if(r1!=r2) { p[r1]=r2; count--; } }
            if(j+1<n && grid[i][j+1]=='1') { int r1=find(p, i*n+j), r2=find(p, i*n+j+1); if(r1!=r2) { p[r1]=r2; count--; } }
        }
        return count;
    }
    private int find(int[] p, int i) { return p[i]==i?i:(p[i]=find(p, p[i])); }
}
← Previous QuestionPrefix and Suffix Search (Optimized Query)
Next Question →Graph Valid Tree