Course4all

Number of Islands

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Union Find.

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])); }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionPrefix and Suffix Search (Optimized Query)
Next Question →Graph Valid Tree