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:
grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]
Output:
1
Explanation:
The entire land area in the upper-left corner is connected, forming one large island. There are no other land masses.
Example 2
Input:
grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]
Output:
3
Explanation:
There are three distinct islands: 1. The 2x2 block in the upper-left. 2. The single land cell in the center. 3. The 2-cell connected landmass in the bottom-right corner.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[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
- C++
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();
}
};
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
DisjointSetclass manages components using two vectors:parentfor storing the root of each element andsizefor balancing the union operations. Initially, each land cell is considered as a separate component. - The
locatefunction with path compression reduces the time complexity of finding the root of an element. - The
mergefunction 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
IslandCounterclass contains thecountIslandsmethod. 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,
getComponentCountreturns the number of distinct roots inparent, 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();
}
}
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()
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
DisjointSetclass 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.
- The
Find and Union Operations:
- The
findmethod recursively finds the root leader of an index, applying path compression to optimize future queries. - The
unionmethod connects two elements and with union by rank, reduces the height of trees, thereby optimizing the structure.
- The
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.
- In the main function,
Result Extraction:
- The total count of separate islands is retrieved by calling the
getIslandCount()method on an instance ofDisjointSetafter all possible unions are performed.
- The total count of separate islands is retrieved by calling the
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.
No comments yet.