Java Program to Find Number of Islands

To find the number of islands in Java, use a grid traversal with DFS by checking each cell and marking connected land cells visited using a method like dfs(), then count how many times you start a new DFS on unvisited land cells.

Examples

Input[[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]

Output3

Input[[1,1,1],[0,1,0],[1,0,1]]

Output1

Input[[0,0,0],[0,0,0],[0,0,0]]

Output0

How to Think About It

Think of the grid as a map where 1 means land and 0 means water. To find islands, scan each cell. When you find land that is not visited, start exploring all connected land cells around it (up, down, left, right) and mark them visited. Each new exploration means a new island.

Algorithm

1

Initialize count of islands to zero.

2

Loop through each cell in the grid.

3

If the cell is land (1) and not visited, increase island count and run DFS to mark all connected land cells visited.

4

DFS checks neighbors (up, down, left, right) and marks connected land cells visited.

5

After scanning all cells, return the island count.

Code

java

public class NumberOfIslands {
    public static int numIslands(int[][] grid) {
        int count = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    dfs(grid, visited, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private static void dfs(int[][] grid, boolean[][] visited, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0 || visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        dfs(grid, visited, i + 1, j);
        dfs(grid, visited, i - 1, j);
        dfs(grid, visited, i, j + 1);
        dfs(grid, visited, i, j - 1);
    }

    public static void main(String[] args) {
        int[][] grid = {
            {1, 1, 0, 0, 0},
            {1, 1, 0, 0, 0},
            {0, 0, 1, 0, 0},
            {0, 0, 0, 1, 1}
        };
        System.out.println(numIslands(grid));
    }
}

Output

3

Dry Run

Let's trace the example grid [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]] through the code

1

Start scanning grid

At cell (0,0), value is 1 and not visited, start DFS and increment count to 1.

2

DFS marks connected land

Mark (0,0), (0,1), (1,0), (1,1) as visited.

3

Continue scanning

Cells (0,2) to (1,4) are water or visited, skip.

4

Find next island

At cell (2,2), value is 1 and not visited, start DFS and increment count to 2.

5

Mark single cell island

Mark (2,2) visited.

6

Find last island

At cell (3,3), value is 1 and not visited, start DFS and increment count to 3.

7

Mark connected land

Mark (3,3) and (3,4) visited.

Step	Island Count	Visited Cells
1	1	(0,0),(0,1),(1,0),(1,1)
2	2	(2,2)
3	3	(3,3),(3,4)

Why This Works

Step 1: Scan each cell

We check every cell to find unvisited land cells which indicate a new island.

Step 2: Use DFS to mark connected land

DFS visits all connected land cells (up, down, left, right) marking them visited to avoid recounting.

Step 3: Count islands

Each time DFS starts on a new unvisited land cell, it means a new island is found, so we increase the count.

Alternative Approaches

Breadth-First Search (BFS)

java

import java.util.LinkedList;
import java.util.Queue;

public class NumberOfIslandsBFS {
    public static int numIslands(int[][] grid) {
        int count = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    count++;
                    Queue<int[]> queue = new LinkedList<>();
                    queue.add(new int[]{i, j});
                    visited[i][j] = true;
                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        for (int k = 0; k < 4; k++) {
                            int x = cell[0] + dx[k];
                            int y = cell[1] + dy[k];
                            if (x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 1 && !visited[x][y]) {
                                queue.add(new int[]{x, y});
                                visited[x][y] = true;
                            }
                        }
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] grid = {
            {1, 1, 0, 0, 0},
            {1, 1, 0, 0, 0},
            {0, 0, 1, 0, 0},
            {0, 0, 0, 1, 1}
        };
        System.out.println(numIslands(grid));
    }
}

BFS uses a queue to explore neighbors level by level; it is iterative and can be easier to understand for some.

Union-Find (Disjoint Set)

java

public class NumberOfIslandsUnionFind {
    private int[] parent;
    private int count;

    public NumberOfIslandsUnionFind(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        parent = new int[m * n];
        count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int id = i * n + j;
                    parent[id] = id;
                    count++;
                } else {
                    parent[i * n + j] = -1;
                }
            }
        }
    }

    public int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
            count--;
        }
    }

    public int getCount() {
        return count;
    }

    public static int numIslands(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        NumberOfIslandsUnionFind uf = new NumberOfIslandsUnionFind(grid);
        int[] dx = {1, 0};
        int[] dy = {0, 1};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 2; k++) {
                        int x = i + dx[k];
                        int y = j + dy[k];
                        if (x < m && y < n && grid[x][y] == 1) {
                            uf.union(i * n + j, x * n + y);
                        }
                    }
                }
            }
        }
        return uf.getCount();
    }

    public static void main(String[] args) {
        int[][] grid = {
            {1, 1, 0, 0, 0},
            {1, 1, 0, 0, 0},
            {0, 0, 1, 0, 0},
            {0, 0, 0, 1, 1}
        };
        System.out.println(numIslands(grid));
    }
}

Union-Find groups connected lands efficiently; good for dynamic connectivity but more complex to implement.

Complexity: O(m*n) time, O(m*n) space

Time Complexity

We visit each cell once, and DFS explores connected cells, so total time is proportional to grid size O(m*n).

Space Complexity

We use a visited array of size m*n and recursion stack in worst case can be O(m*n).

Which Approach is Fastest?

DFS and BFS have similar time and space complexity; Union-Find can be faster for multiple queries but is more complex.

Approach	Time	Space	Best For
DFS	O(m*n)	O(m*n)	Simple and intuitive for single grid
BFS	O(m*n)	O(m*n)	Iterative alternative to DFS
Union-Find	O(m*n)	O(m*n)	Efficient for dynamic connectivity or multiple queries