Number of Islands

1 min readUpdated 3 July 2025

Problem Statement

In the given task, we are provided with a two-dimensional grid representing a map where '1' represents land and '0' represents water. The objective is to determine how many discrete islands can be found in this grid. An island is defined as a cluster of adjacent lands, where adjacency is confined to horizontal or vertical directions. Importantly, any land segment located on the edge of the grid is considered to be surrounded by water, isolating these edge segments from creating trans-grid connections.

Examples

Example 1

Input:

EXAMPLE_ENTITY

grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

The entire land area in the upper-left corner is connected, forming one large island. There are no other land masses.

Example 2

Input:

EXAMPLE_ENTITY

grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

There are three distinct islands:
The 2x2 block in the upper-left.
The single land cell in the center.
The 2-cell connected landmass in the bottom-right corner.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

Approach and Intuition

The key idea is to scan the grid and count how many separate clusters of land cells ('1') exist. This is done by:

Iterating through each cell of the grid.
When a land cell is found, use Depth-First Search (DFS) or Breadth-First Search (BFS) to mark all connected land cells as visited (e.g., by setting them to '0').
Every time a new unvisited land cell is found, increment the island count and begin a new traversal to mark that island.
Repeat until all cells are processed.

This approach guarantees that each distinct group of connected land is counted exactly once, meeting the problem’s requirement to return the number of islands.

Solutions

CPP
class DisjointSet {
public:
  DisjointSet(vector<vector<char>>& matrix) {
    componentCount = 0;
    int rows = matrix.size();
    int cols = matrix[0].size();
    for (int row = 0; row < rows; ++row) {
      for (int col = 0; col < cols; ++col) {
        if (matrix[row][col] == '1') {
          parent.push_back(row * cols + col);
          ++componentCount;
        }
        else parent.push_back(-1);
        size.push_back(0);
      }
    }
  }
    
  int locate(int i) { // Path compression optimization
    if (parent[i] != i) parent[i] = locate(parent[i]);
    return parent[i];
  }
    
  void merge(int x, int y) { // Union by size
    int rootX = locate(x);
    int rootY = locate(y);
    if (rootX != rootY) {
      if (size[rootX] > size[rootY]) parent[rootY] = rootX;
      else if (size[rootX] < size[rootY]) parent[rootX] = rootY;
      else {
        parent[rootY] = rootX;
        size[rootX] += 1;
      }
      --componentCount;
    }
  }
    
  int getComponentCount() const {
    return componentCount;
  }
    
private:
  vector<int> parent;
  vector<int> size;
  int componentCount;
};
    
class IslandCounter {
public:
  int countIslands(vector<vector<char>>& matrix) {
    int rowLength = matrix.size();
    if (rowLength == 0) return 0;
    int colLength = matrix[0].size();
    
    DisjointSet ds(matrix);
    for (int row = 0; row < rowLength; ++row) {
      for (int col = 0; col < colLength; ++col) {
        if (matrix[row][col] == '1') {
          matrix[row][col] = '0';
          if (row - 1 >= 0 && matrix[row-1][col] == '1') ds.merge(row * colLength + col, (row-1) * colLength + col);
          if (row + 1 < rowLength && matrix[row+1][col] == '1') ds.merge(row * colLength + col, (row+1) * colLength + col);
          if (col - 1 >= 0 && matrix[row][col-1] == '1') ds.merge(row * colLength + col, row * colLength + col - 1);
          if (col + 1 < colLength && matrix[row][col+1] == '1') ds.merge(row * colLength + col, row * colLength + col + 1);
        }
      }
    }
    
    return ds.getComponentCount();
  }
};
Powered by Vultr AgentBeta

The C++ solution provided uses the Disjoint Set (Union-Find) data structure to efficiently handle the "Number of Islands" problem, where you need to count distinct islands on a 2D grid marked with '1's (land) and '0's (water).

The DisjointSet class manages components using two vectors: parent for storing the root of each element and size for balancing the union operations. Initially, each land cell is considered as a separate component.
The locate function with path compression reduces the time complexity of finding the root of an element.
The merge function unites two components using the union by size strategy, which ensures that the smaller tree is always merged under the root of the larger tree. This helps in keeping the disjoint set tree flat and optimizes subsequent union and find operations.
The IslandCounter class contains the countIslands method. It iterates through each cell in the grid, marking visited cells to prevent recounting and merging adjacent land cells to form islands using the Disjoint Set methods.
At the end of processing, getComponentCount returns the number of distinct roots in parent, which corresponds to the number of islands.

This design highlights optimal management of dynamically merging sets and tracking their counts with minimal overhead, effectively solving the problem using depth-first characteristics without explicit recursion or stack/queue usage thanks to the Disjoint Set structure.

JAVA
class Solution {
    class DisjointSet {
        int componentCount;
        int[] parent;
        int[] rank;
    
        public DisjointSet(char[][] grid) {
            componentCount = 0;
            int rows = grid.length;
            int cols = grid[0].length;
            parent = new int[rows * cols];
            rank = new int[rows * cols];
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    if (grid[i][j] == '1') {
                        parent[i * cols + j] = i * cols + j;
                        ++componentCount;
                    }
                    rank[i * cols + j] = 0;
                }
            }
        }
    
        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) {
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
                componentCount--;
            }
        }
    
        public int getComponentCount() {
            return componentCount;
        }
    }
    
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
    
        int numRows = grid.length;
        int numCols = grid[0].length;
        int islandCount = 0;
        DisjointSet ds = new DisjointSet(grid);
        for (int row = 0; row < numRows; ++row) {
            for (int col = 0; col < numCols; ++col) {
                if (grid[row][col] == '1') {
                    grid[row][col] = '0';
                    if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                        ds.union(row * numCols + col, (row - 1) * numCols + col);
                    }
                    if (row + 1 < numRows && grid[row + 1][col] == '1') {
                        ds.union(row * numCols + col, (row + 1) * numCols + col);
                    }
                    if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                        ds.union(row * numCols + col, row * numCols + col - 1);
                    }
                    if (col + 1 < numCols && grid[row][col + 1] == '1') {
                        ds.union(row * numCols + col, row * numCols + col + 1);
                    }
                }
            }
        }
    
        return ds.getComponentCount();
    }
}
Powered by Vultr AgentBeta

The Java solution for the Number of Islands problem uses a Disjoint Set (also known as Union-Find) data structure to efficiently track and merge connected components of land ('1's) in a 2D grid. Here's how this implementation works:

Initialization:
- Instantiate a Disjoint Set with arrays to keep track of each cell's parent and rank.
- Set the parent of each land cell to itself, effectively making each land cell its own component initially.
Union Operation:
- Connect adjacent land cells. If two adjacent cells belong to different sets, merge these sets using the union operation, which employs the path compression and union by rank techniques to optimize the merging process.
Path Compression:
- During the find operation, if a cell points not directly to itself (i.e., it is not its own parent), recursively adjust it and all its ancestors to point directly to the root parent, flattening the structure and speeding up future find operations.
Union by Rank:
- When merging two sets, always attach the shorter tree under the root of the taller tree, which keeps the structure flatter and thus speeds up future operations.
Counting Islands:
- Iterate over all cells in the grid. When a land cell is found, make adjacent land cells part of the same set by using the union operation. As sets are being merged, decrease an island count.
- Cells are converted to '0' once visited to prevent redundant visits.

Finally, the component count remaining in the DisjointSet instance gives the total number of distinct islands in the grid. This count is returned as the result. The algorithm efficiently handles the merging of areas belonging to the same island, and the union-find data structure allows nearly constant time complexity for union and find operations on average.

PYTHON
class DisjointSet:
    def __init__(self, matrix):
        self.islands = 0
        rows, cols = len(matrix), len(matrix[0])
        self.leader = []
        self.tree_rank = []
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == "1":
                    self.leader.append(i * cols + j)
                    self.islands += 1
                else:
                    self.leader.append(-1)
                self.tree_rank.append(0)
    
    def find(self, idx):
        if self.leader[idx] != idx:
            self.leader[idx] = self.find(self.leader[idx])
        return self.leader[idx]
    
    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP != rootQ:
            if self.tree_rank[rootP] > self.tree_rank[rootQ]:
                self.leader[rootQ] = rootP
            elif self.tree_rank[rootP] < self.tree_rank[rootQ]:
                self.leader[rootP] = rootQ
            else:
                self.leader[rootQ] = rootP
                self.tree_rank[rootP] += 1
            self.islands -= 1
    
    def getIslandCount(self):
        return self.islands
    
    
class IslandCounter:
    def countIslands(self, matrix):
        if not matrix or not matrix[0]:
            return 0
    
        row_count = len(matrix)
        column_count = len(matrix[0])
        ds = DisjointSet(matrix)
    
        for row in range(row_count):
            for col in range(column_count):
                if matrix[row][col] == "1":
                    matrix[row][col] = "0"
                    if row > 0 and matrix[row - 1][col] == "1":
                        ds.union(row * column_count + col, (row - 1) * column_count + col)
                    if row < row_count - 1 and matrix[row + 1][col] == "1":
                        ds.union(row * column_count + col, (row + 1) * column_count + col)
                    if col > 0 and matrix[row][col - 1] == "1":
                        ds.union(row * column_count + col, row * column_count + col - 1)
                    if col < column_count - 1 and matrix[row][col + 1] == "1":
                        ds.union(row * column_count + col, row * column_count + col + 1)
    
        return ds.getIslandCount()
Powered by Vultr AgentBeta

This Python3 solution tackles the "Number of Islands" problem by employing the Disjoint Set (Union-Find) data structure efficiently. Understand the following components of the implemented solution:

Initialization:
- The DisjointSet class is initiated with a matrix. It sets up leader and rank arrays. Each cell in the matrix that contains "1" is treated as a potential individual island.
Find and Union Operations:
- The find method recursively finds the root leader of an index, applying path compression to optimize future queries.
- The union method connects two elements and with union by rank, reduces the height of trees, thereby optimizing the structure.
Counting Islands:
- In the main function, countIslands, matrices are traversed, and each land cell identified as "1" is processed. Adjacent cells are checked in four possible directions (up, down, left, right), and union operations are applied if they are part of the same land mass, effectively marking them as part of the same island.
- Each successful union between cells decrements the island count, since it merges two separate islands into one.
Result Extraction:
- The total count of separate islands is retrieved by calling the getIslandCount() method on an instance of DisjointSet after all possible unions are performed.

This approach efficiently keeps track of connected components in the matrix using the dynamic connectivity of the union-find structure, making it suitable for solving problems related to cluster or connectivity detection in grids.

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.

Number of Islands

1 min readUpdated 3 July 2025

Problem Statement

Examples

Example 1

Input:

EXAMPLE_ENTITY

grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

The entire land area in the upper-left corner is connected, forming one large island. There are no other land masses.

Example 2

Input:

EXAMPLE_ENTITY

grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

There are three distinct islands:
The 2x2 block in the upper-left.
The single land cell in the center.
The 2-cell connected landmass in the bottom-right corner.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

Approach and Intuition

The key idea is to scan the grid and count how many separate clusters of land cells ('1') exist. This is done by:

Iterating through each cell of the grid.
When a land cell is found, use Depth-First Search (DFS) or Breadth-First Search (BFS) to mark all connected land cells as visited (e.g., by setting them to '0').
Every time a new unvisited land cell is found, increment the island count and begin a new traversal to mark that island.
Repeat until all cells are processed.

This approach guarantees that each distinct group of connected land is counted exactly once, meeting the problem’s requirement to return the number of islands.

Solutions

CPP
class DisjointSet {
public:
  DisjointSet(vector<vector<char>>& matrix) {
    componentCount = 0;
    int rows = matrix.size();
    int cols = matrix[0].size();
    for (int row = 0; row < rows; ++row) {
      for (int col = 0; col < cols; ++col) {
        if (matrix[row][col] == '1') {
          parent.push_back(row * cols + col);
          ++componentCount;
        }
        else parent.push_back(-1);
        size.push_back(0);
      }
    }
  }
    
  int locate(int i) { // Path compression optimization
    if (parent[i] != i) parent[i] = locate(parent[i]);
    return parent[i];
  }
    
  void merge(int x, int y) { // Union by size
    int rootX = locate(x);
    int rootY = locate(y);
    if (rootX != rootY) {
      if (size[rootX] > size[rootY]) parent[rootY] = rootX;
      else if (size[rootX] < size[rootY]) parent[rootX] = rootY;
      else {
        parent[rootY] = rootX;
        size[rootX] += 1;
      }
      --componentCount;
    }
  }
    
  int getComponentCount() const {
    return componentCount;
  }
    
private:
  vector<int> parent;
  vector<int> size;
  int componentCount;
};
    
class IslandCounter {
public:
  int countIslands(vector<vector<char>>& matrix) {
    int rowLength = matrix.size();
    if (rowLength == 0) return 0;
    int colLength = matrix[0].size();
    
    DisjointSet ds(matrix);
    for (int row = 0; row < rowLength; ++row) {
      for (int col = 0; col < colLength; ++col) {
        if (matrix[row][col] == '1') {
          matrix[row][col] = '0';
          if (row - 1 >= 0 && matrix[row-1][col] == '1') ds.merge(row * colLength + col, (row-1) * colLength + col);
          if (row + 1 < rowLength && matrix[row+1][col] == '1') ds.merge(row * colLength + col, (row+1) * colLength + col);
          if (col - 1 >= 0 && matrix[row][col-1] == '1') ds.merge(row * colLength + col, row * colLength + col - 1);
          if (col + 1 < colLength && matrix[row][col+1] == '1') ds.merge(row * colLength + col, row * colLength + col + 1);
        }
      }
    }
    
    return ds.getComponentCount();
  }
};
Powered by Vultr AgentBeta

The DisjointSet class manages components using two vectors: parent for storing the root of each element and size for balancing the union operations. Initially, each land cell is considered as a separate component.
The locate function with path compression reduces the time complexity of finding the root of an element.
The merge function unites two components using the union by size strategy, which ensures that the smaller tree is always merged under the root of the larger tree. This helps in keeping the disjoint set tree flat and optimizes subsequent union and find operations.
The IslandCounter class contains the countIslands method. It iterates through each cell in the grid, marking visited cells to prevent recounting and merging adjacent land cells to form islands using the Disjoint Set methods.
At the end of processing, getComponentCount returns the number of distinct roots in parent, which corresponds to the number of islands.

JAVA
class Solution {
    class DisjointSet {
        int componentCount;
        int[] parent;
        int[] rank;
    
        public DisjointSet(char[][] grid) {
            componentCount = 0;
            int rows = grid.length;
            int cols = grid[0].length;
            parent = new int[rows * cols];
            rank = new int[rows * cols];
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    if (grid[i][j] == '1') {
                        parent[i * cols + j] = i * cols + j;
                        ++componentCount;
                    }
                    rank[i * cols + j] = 0;
                }
            }
        }
    
        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) {
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
                componentCount--;
            }
        }
    
        public int getComponentCount() {
            return componentCount;
        }
    }
    
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
    
        int numRows = grid.length;
        int numCols = grid[0].length;
        int islandCount = 0;
        DisjointSet ds = new DisjointSet(grid);
        for (int row = 0; row < numRows; ++row) {
            for (int col = 0; col < numCols; ++col) {
                if (grid[row][col] == '1') {
                    grid[row][col] = '0';
                    if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                        ds.union(row * numCols + col, (row - 1) * numCols + col);
                    }
                    if (row + 1 < numRows && grid[row + 1][col] == '1') {
                        ds.union(row * numCols + col, (row + 1) * numCols + col);
                    }
                    if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                        ds.union(row * numCols + col, row * numCols + col - 1);
                    }
                    if (col + 1 < numCols && grid[row][col + 1] == '1') {
                        ds.union(row * numCols + col, row * numCols + col + 1);
                    }
                }
            }
        }
    
        return ds.getComponentCount();
    }
}
Powered by Vultr AgentBeta

Initialization:
- Instantiate a Disjoint Set with arrays to keep track of each cell's parent and rank.
- Set the parent of each land cell to itself, effectively making each land cell its own component initially.
Union Operation:
- Connect adjacent land cells. If two adjacent cells belong to different sets, merge these sets using the union operation, which employs the path compression and union by rank techniques to optimize the merging process.
Path Compression:
- During the find operation, if a cell points not directly to itself (i.e., it is not its own parent), recursively adjust it and all its ancestors to point directly to the root parent, flattening the structure and speeding up future find operations.
Union by Rank:
- When merging two sets, always attach the shorter tree under the root of the taller tree, which keeps the structure flatter and thus speeds up future operations.
Counting Islands:
- Iterate over all cells in the grid. When a land cell is found, make adjacent land cells part of the same set by using the union operation. As sets are being merged, decrease an island count.
- Cells are converted to '0' once visited to prevent redundant visits.

PYTHON
class DisjointSet:
    def __init__(self, matrix):
        self.islands = 0
        rows, cols = len(matrix), len(matrix[0])
        self.leader = []
        self.tree_rank = []
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == "1":
                    self.leader.append(i * cols + j)
                    self.islands += 1
                else:
                    self.leader.append(-1)
                self.tree_rank.append(0)
    
    def find(self, idx):
        if self.leader[idx] != idx:
            self.leader[idx] = self.find(self.leader[idx])
        return self.leader[idx]
    
    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP != rootQ:
            if self.tree_rank[rootP] > self.tree_rank[rootQ]:
                self.leader[rootQ] = rootP
            elif self.tree_rank[rootP] < self.tree_rank[rootQ]:
                self.leader[rootP] = rootQ
            else:
                self.leader[rootQ] = rootP
                self.tree_rank[rootP] += 1
            self.islands -= 1
    
    def getIslandCount(self):
        return self.islands
    
    
class IslandCounter:
    def countIslands(self, matrix):
        if not matrix or not matrix[0]:
            return 0
    
        row_count = len(matrix)
        column_count = len(matrix[0])
        ds = DisjointSet(matrix)
    
        for row in range(row_count):
            for col in range(column_count):
                if matrix[row][col] == "1":
                    matrix[row][col] = "0"
                    if row > 0 and matrix[row - 1][col] == "1":
                        ds.union(row * column_count + col, (row - 1) * column_count + col)
                    if row < row_count - 1 and matrix[row + 1][col] == "1":
                        ds.union(row * column_count + col, (row + 1) * column_count + col)
                    if col > 0 and matrix[row][col - 1] == "1":
                        ds.union(row * column_count + col, row * column_count + col - 1)
                    if col < column_count - 1 and matrix[row][col + 1] == "1":
                        ds.union(row * column_count + col, row * column_count + col + 1)
    
        return ds.getIslandCount()
Powered by Vultr AgentBeta

This Python3 solution tackles the "Number of Islands" problem by employing the Disjoint Set (Union-Find) data structure efficiently. Understand the following components of the implemented solution:

Initialization:
- The DisjointSet class is initiated with a matrix. It sets up leader and rank arrays. Each cell in the matrix that contains "1" is treated as a potential individual island.
Find and Union Operations:
- The find method recursively finds the root leader of an index, applying path compression to optimize future queries.
- The union method connects two elements and with union by rank, reduces the height of trees, thereby optimizing the structure.
Counting Islands:
- In the main function, countIslands, matrices are traversed, and each land cell identified as "1" is processed. Adjacent cells are checked in four possible directions (up, down, left, right), and union operations are applied if they are part of the same land mass, effectively marking them as part of the same island.
- Each successful union between cells decrements the island count, since it merges two separate islands into one.
Result Extraction:
- The total count of separate islands is retrieved by calling the getIslandCount() method on an instance of DisjointSet after all possible unions are performed.

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.