Solution: Number of Islands

Let's solve the Number of Islands problem using the Union Find pattern.

We'll cover the following

Statement
Solution

We can use the Union Find pattern to efficiently determine the number of disjoint sets (islands) and effectively merge them when they share a common land. We iterate through each cell of the given grid. If the cell is water, $0$ , we ignore it and move to the next cell. However, if it’s a land cell, $1$ , we connect it with all its adjacent land cells using the union method. This step merges connected land regions into cohesive islands. By marking visited cells and checking neighboring cells, the algorithm efficiently traverses the grid, identifying and merging connected land components. Finally, we count and return the number of connected components in the Union Find data structure corresponding to the total number of islands in the grid.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

Let’s start by counting the number of cell 1s in the grid. This can be done by declaring an instance of the Union Find class. Here’s how the Union Find class is initialized:

A variable, count, is initialized to 0.
A list, parent, is initialized against each element, grid[i][j], in the grid as follows:
- If we encounter a cell 1, we append the current index, i * n + j, of the grid according to the row major orderIn row major order, elements of a multi-dimensional array are arranged sequentially, row by row, which means filling all the indexes of the first row and moving on to the next row. and increment count by 1 (see lines 18–20 in the Union Find class).
- If a cell 0 is encountered, we append −1 to the array (see line 22 in the Union Find class) because cell 0s in the grid will be ignored anyway.

At the end of this traversal, count will contain the number of occurrences of cell 1 in the grid (see line 27 in main.java). Currently, all the cells having 1 are disconnected from each other. Let’s see how we can connect them to form an island and count the total number of islands in the grid.

main.java

UnionFind.java

import java.util.*;
public class UnionFind {
    // Initializing the parent list and count variable by traversing the grid
    private List<Integer> parent;
    private List<Integer> rank;
    private int count;
    public UnionFind(List<List<Character>> grid) {
        int m = grid.size();
        int n = grid.get(0).size();
        this.parent = new ArrayList<Integer>();
        this.rank = new ArrayList<Integer>();
        this.count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == '1') {
                    parent.add(i * n + j);
                    this.count += 1;
                } else {
                    this.parent.add(-1);
                }
                this.rank.add(1);
            }
        }
    }
    public List<Integer> getParent() {
        return this.parent;
    }
    // Function to return the number of connected components consisting of 1s
    public int getCount() {
        return this.count;
    }
    // Function to connect components
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 != p2) {
            // The absolute value of the root node represents the size of this union
            // Make the one with larger size be the new parent
            if (this.rank.get(p1) > this.rank.get(p2)) {
                this.parent.set(p2, p1);
            } else if (this.rank.get(p1) < this.rank.get(p2)) {
                this.parent.set(p1, p2);
            } else {
                this.parent.set(p2, p1);
                this.rank.set(p1, this.rank.get(p1) + 1);
            }
            count--;
        }
    }
    // Function to find the root parent of a node
    public int find(int v) {
        if (this.parent.get(v) != v) {
            this.parent.set(v, this.find(this.parent.get(v)));
        }
        return this.parent.get(v);
    }
}

Storing the indexes of grid value 1s in a parent list

For now, we have the count of the total number of cell 1s in the grid stored in count. However, we aim to connect all the neighboring cell 1s on the bottom, and right into components. This will reduce our count from the total number of cell 1s to the total number of connected components of cell 1s.

We can achieve this by using the union find algorithm to connect neighboring cell 1s, decrementing the count whenever a connection is made.

We’ll update the code by traversing each element of the grid as follows:

If a cell 1 is encountered, we do the following:
- We update the value of the grid from 1 to 0.
- We check the value of each neighbor at the bottom and right of the current element. If the value is 1, we perform the union operation between the current element and its neighbor, which consists of 1.
- Inside the union operation, we check if the parent of the current element and its neighbor is different.
  - If so, we connect these two cells and decrement count by $1$ .
  - Otherwise, if their parent is the same, they are already part of a connected component, so we do not decrement count.
At the end of the traversal, count will contain the total number of islands.

The slides below illustrate how we would like the algorithm to run:

Press + to interact

main.java

UnionFind.java

import java.util.*;
class NoOfIslands {
    public static void printGrid(List<List<Character>> grid) {
        for (int i = 0; i < grid.size(); i++) {
            System.out.print("\t\t[");
            for (int j = 0; j < grid.get(i).size() - 1; j++) {
                System.out.print("'" + grid.get(i).get(j) + "', ");
            }
            System.out.println("'" + grid.get(i).get(grid.get(i).size() - 1) + "']");
        }
    }
    public static int numIslands(List<List<Character>> grid) {
        // If the grid is empty, then return 0
        if (grid.size() == 0)
            return 0;
        // Get the number of rows and columns in the grid
        int cols = grid.get(0).size();
        int rows = grid.size();
        // Create a Union Find object to represent the islands in the grid
        UnionFind unionFind = new UnionFind(grid);
        // Iterate over each cell in the grid
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                // If the current cell is a land, then mark it as visited
                if (grid.get(r).get(c) == '1') {
                    // Check the horizontal and vertical neighbors of the current cell
                    // If any of the neighbors are also lands, then unite the current cell with the neighbor
                    if (r + 1 < rows && grid.get(r + 1).get(c) == '1')
                        unionFind.union(r * cols + c, (r + 1) * cols + c);
                    if (c + 1 < cols && grid.get(r).get(c + 1) == '1')
                        unionFind.union(r * cols + c, r * cols + c + 1);
                }
            }
        }
        // Return the number of islands in the grid
        int count = unionFind.getCount();
        return count;
    }
    // Driver code
    public static void main(String args[]) {
        // Example grid
        // Test case 01
        List<List<Character>> grid1 = Arrays.asList(
                Arrays.asList('1', '1', '1'),
                Arrays.asList('0', '1', '0'),
                Arrays.asList('1', '0', '0'),
                Arrays.asList('1', '0', '1')
        );
        // Test case 02
        List<List<Character>> grid2 = Arrays.asList(
                Arrays.asList('1', '1', '1', '1', '0'),
                Arrays.asList('1', '0', '0', '0', '1'),
                Arrays.asList('1', '0', '0', '1', '1'),
                Arrays.asList('0', '1', '0', '1', '0'),
                Arrays.asList('1', '1', '0', '1', '1')
        );
        // Test case 03
        List<List<Character>> grid3 = Arrays.asList(
                Arrays.asList('1', '1', '1', '1', '0'),
                Arrays.asList('1', '0', '0', '0', '1'),
                Arrays.asList('1', '1', '1', '1', '1'),
                Arrays.asList('0', '1', '0', '1', '0'),
                Arrays.asList('1', '1', '0', '1', '1')
        );
        // Test case 04
        List<List<Character>> grid4 = Arrays.asList(
                Arrays.asList('1', '0', '1', '0', '1'),
                Arrays.asList('0', '1', '0', '1', '0'),
                Arrays.asList('1', '0', '1', '0', '1'),
                Arrays.asList('0', '1', '0', '1', '0'),
                Arrays.asList('1', '0', '1', '0', '1')
        );
        // Test case 05
        List<List<Character>> grid5 = Arrays.asList(
                Arrays.asList('1', '0', '1'),
                Arrays.asList('0', '0', '0'),
                Arrays.asList('1', '0', '1')
        );
        List<List<List<Character>>> inputs = Arrays.asList(grid1, grid2, grid3, grid4, grid5);
        for (int i = 0; i < inputs.size(); i++) {
            System.out.println((i + 1) + ".\t Grid: ");
            printGrid(inputs.get(i));
            System.out.println("\n\t Output: " + numIslands(inputs.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Number of Islands

main.java

UnionFind.java

import java.util.*;
class NoOfIslands {
    public static int numIslands(List<List<Character>> grid) {
        if (grid.size() == 0)
            return 0;
        int cols = grid.get(0).size();
        int rows = grid.size();
        UnionFind unionFind = new UnionFind(grid);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid.get(r).get(c) == '1') {
                    if (r + 1 < rows && grid.get(r + 1).get(c) == '1')
                        unionFind.union(r * cols + c, (r + 1) * cols + c);
                    if (c + 1 < cols && grid.get(r).get(c + 1) == '1')
                        unionFind.union(r * cols + c, r * cols + c + 1);
                }
            }
        }
        int count = unionFind.getCount();
        return count;
    }
    public static void printGrid(List<List<Character>> grid) {
        for (int i = 0; i < grid.size(); i++) {
            System.out.print("\t\t[");
            for (int j = 0; j < grid.get(i).size() - 1; j++) {
                System.out.print("'" + grid.get(i).get(j) + "', ");
            }
            System.out.println("'" + grid.get(i).get(grid.get(i).size() - 1) + "']");
        }
    }
    public static void main(String args[]) {
        // Example grid
        List<List<Character>> grid1 = Arrays.asList(
                Arrays.asList('1', '1', '1'),
                Arrays.asList('0', '1', '0'),
                Arrays.asList('1', '0', '0'),
                Arrays.asList('1', '0', '1')
        );
        List<List<Character>> grid2 = Arrays.asList(
                Arrays.asList('1', '1', '1', '1', '0'),
                Arrays.asList('1', '0', '0', '0', '1'),
                Arrays.asList('1', '0', '0', '1', '1'),
                Arrays.asList('0', '1', '0', '1', '0'),
                Arrays.asList('1', '1', '0', '1', '1')
        );
        List<List<Character>> grid3 = Arrays.asList(
                Arrays.asList('1', '1', '1', '1', '0'),
                Arrays.asList('1', '0', '0', '0', '1'),
                Arrays.asList('1', '1', '1', '1', '1'),
                Arrays.asList('0', '1', '0', '1', '0'),
                Arrays.asList('1', '1', '0', '1', '1')
        );
        List<List<Character>> grid4 = Arrays.asList(
                Arrays.asList('1', '0', '1', '0', '1'),
                Arrays.asList('0', '1', '0', '1', '0'),
                Arrays.asList('1', '0', '1', '0', '1'),
                Arrays.asList('0', '1', '0', '1', '0'),
                Arrays.asList('1', '0', '1', '0', '1')
        );
        List<List<Character>> grid5 = Arrays.asList(
                Arrays.asList('1', '0', '1'),
                Arrays.asList('0', '0', '0'),
                Arrays.asList('1', '0', '1')
        );
        List<List<List<Character>>> inputs = Arrays.asList(grid1, grid2, grid3, grid4, grid5);
        for (int i = 0; i < inputs.size(); i++) {
            System.out.println((i + 1) + ".\t Grid: ");
            printGrid(inputs.get(i));
            System.out.println("\n\t Output: " + numIslands(inputs.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Number of Islands

Solution summary

To recap, the solution to this problem can be divided into the following three parts:

Count all occurrences of cell 1s in the grid.
Traverse the grid and if a cell 1 is encountered, perform the union operation between the neighboring cell 1s to connect them into a single component.
Decrement count by $1$ only if the current element and its neighboring cell 1s aren’t already part of a connected component.

Time complexity

The time complexity of this solution is $O(m × n)$ , where $m$ is the number of rows, and $n$ is the number of columns.

Space complexity

The space complexity of this solution is $O(m × n)$ , as required by the Union Find class.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.

Getting Started

Two Pointers

Fast and Slow Pointers

Sliding Window

Merge Intervals

In-Place Manipulation of a Linked List

Two Heaps

K-way merge

Top K Elements

Modified Binary Search

Subsets

Greedy Techniques

Backtracking

Dynamic Programming

Cyclic Sort

Topological Sort

Sort and Search

Matrices

Stacks

Graphs

Tree Depth-First Search

Tree Breadth-First Search

Trie

Hash Maps

Knowing What to Track

Union Find

Custom Data Structures

Bitwise Manipulation

Challenge Yourself

Conclusion

Solution: Number of Islands

Statement

Solution

Step-by-step solution construction

Just the code

Solution summary

Time complexity

Space complexity